[백준/C & C++] 1764 듣보잡

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp(const void* a, const void* b)
{
	return strcmp((char*)a, (char*)b);
}

typedef struct
{
	char s[21];
} name;
int main()
{
	int n, m, cnt=0;
	scanf("%d %d", &n, &m);
	name* arr = (name*)malloc(sizeof(name) * (n + m));
	name* result = (name*)malloc(sizeof(name) * (n + m));
	for (int i = 0; i < n + m; i++) scanf("%s", &arr[i].s);

	qsort(arr, n + m, sizeof(name), cmp);

	for (int i = 0; i < n + m-1; i++)
	{
		if (!strcmp(arr[i].s, arr[i + 1].s))
		{
			strcpy(result[cnt].s, arr[i].s);
			i++;
			cnt++;
		}
	}

	printf("%d\n", cnt);
	for (int i = 0; i < cnt; i++) printf("%s\n", result[i].s);
    	free(arr);
    	free(result);
	return 0;
}

C++

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;

bool cmp(string a, string b)
{
	return a < b;
}

int main()
{
	int n, m, index=0;
	cin >> n >> m;
	string* input = new string[n + m];
	string* result = new string[n + m];
	for (int i = 0; i < n + m; i++) cin >> input[i];
	sort(input, input + n + m, cmp);

	for (int i = 0; i < n + m - 1; i++)
	{
		if (!input[i].compare(input[i+1]))
		{
			result[index] = input[i];
			i++;
			index++;
		}
	}

	cout << index << "\n";
	for (int i = 0; i < index; i++) cout << result[i] << "\n";

	delete[]input;
	delete[]result;
	return 0;
}

코드 설명

c++은 stirng을 이용했는데, c의 경우에는 string이 없기에 구조체를 이용해서 이름을 저장했다. 듣도 못한 사람과 보도 못한 사람을 c++ input[i]에,  c는 input[i].s에 저장한다. 이후 입력받은 이름들을 정렬한다. c++의 경우에는 sort함수를 사용했고, 문자열을 비교하는 cmp함수를 만들었다. c는 qsort를 사용했고, c++에서처럼 cmp함수를 만들었다. 

 

듣도 못한 사람의 명단에는 중복이 없고 이는 보도 못한 사람의 경우에도 마찬가지이기에 듣도 보도 못한 사람의 경우에는 2번 이름이 등장할 것이다! 이제 이를 이용해서 result배열에 결과를 저장한다. 반복문을 돌면서 i와 i+1에 저장된 이름이 같을 경우에는 result배열에 이름을 저장하고 그 수를 저장하는 값인 index를 1씩 증가시킨다. i+1번째에 있는 값은 i+2와 비교할 필요가 없으므로 i++해준다.

 

듣도 보도 못한 사람의 수를 출력하고, 줄을 바꾼 뒤에 그 명단을 반복문을 이용해 출력한다. 동적배열들을 해제하고 프로그램을 종료한다. 

 

느낀 점

처음에는 다른 방식으로 도전했다가 시간초과가 됐다. 그때 짠 방식은 듣도 못한 사람의 이름을 저장하는 배열, 보도 못한 사람의 배열을 저장하는 배열을 각각 만들어서 이름들을 입력받고 정렬한다. 그 뒤에 이진탐색을 이용해서 값을 찾으면 strcpy함수를 이용해서 결과를 저장하는 배열에 이름을 저장하고, cnt를 증가시켰다.

 

감이 잘 잡히지 않아서 구글링하다가 아래 링크한 글에서 아이디어를 얻었다! 

https://531522szerodesire.tistory.com/68

백준 1764 : 듣보잡 (C언어)

그래서 글에서 소개하는 방식대로 코드를 짜서 통과했다. 문제를 더 많이 풀어보면서 머릿속에 아이디어를 채워나가야한다고 생각했던 문제였다.