[백준/C & C++] 1302 베스트셀러

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

1302번: 베스트셀러

 

코드 (C)

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

int compare(const void* a, const void* b);

int main()
{
	int n, count[1001] = {0,}, j = 0, max = -1;
	scanf("%d", &n);
	char book[1001][51];

	for (int i = 0; i < n; i++) scanf("%s", &book[i]);

	qsort(book, n, sizeof(book[0]), compare);

	for (int i = 1; i < n; i++)
	{
		if (!strcmp(book[j], book[i])) count[j]++;
		else j = i;
	}

	for (int i = 0; i < n; i++) if (max < count[i])max = count[i];
	
	for (int i = 0; i < n; i++)
	{
		if (max == count[i])
		{
			printf("%s\n", book[i]);
			break;
		}
	}
	return 0;
}

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

코드 (C++)

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

int main()
{
	int n, j=0;
	cin >> n;
	string* arr = new string[n];
	int* cnt = new int[n];

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		cnt[i] = 0;
	}

	sort(arr, arr + n);

	for (int i = 1; i < n; i++)
	{
		if (arr[j] == arr[i]) cnt[j]++;
		else j = i;
	}

	int max = -1;
	for (int i = 0; i < n; i++)
	{
		if (max < cnt[i]) max = cnt[i];
	}

	for (int i = 0; i < n; i++)
	{
		if (max == cnt[i])
		{
			cout << arr[i];
			break;
		}
	}

	delete[]arr;
	delete[]cnt;
	return 0;
}

코드 설명

먼저 책의 개수 n을 입력받는다.

책들의 이름을 반복문을 사용해서 입력받는다. 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력해야 하므로 바로 사전 순으로 정렬한다. 

 

c는 qsort를 사용했고, compare함수를 작성했다. compare 함수는 반환값을 함수의 결과로 가지는데, 이 함수는 strcmp함수이다. strcmp함수는 두 개의 문자열을 비교해서 1,0,-1을 반환하는데, 1은 a가 사전에서 더 뒤에 위치한다는 뜻이고, 0은 같은 문자열, -1은 a가 사전에서 더 앞에 위치한다는 뜻이다. 그래서 1일 경우에는 교환이 이루어진다. c++은 algorithm헤더파일 내 sort함수를 사용해서 사전 순으로 정렬했다.

 

반복문을 이용해서 개수를 센다. j를 비교기준 값이 저장된 인덱스로 사용한다. c는 strcmp 함수가 비교하는 문자열이 같으면 0을 반환하기 때문에 strcmp함수 앞에 !를 써서  두 개의 문자열이 같은 경우에 if에 해당하게 했다.

두 개의 문자열이 같으면 cnt 배열의 j번째 인덱스에 저장된 값을 1 증가시킨다. 만약 두 개의 문자열이 다른 경우에는 j=i로 해서 비교대상 값을 변경한다. 

 

위의 반복문이 끝나면 각각의 단어가 나온 횟수가 배열에 저장되어 있다!  가장 많이 팔린 책이 무엇인지 알기 위해 반복문을 사용해서 책이 팔린 max값을 구한다. max를 이용해서 마지막 반복문을 돈다. 만약 cnt[i]==max라면, 값을 출력하고 반복문을 탈출한 후 프로그램을 종료한다. (max값이 여러 개일 경우에 사전 순으로 가장 앞서는 값을 출력하고 종료해야 하기에 break;를 사용했다.)

느낀 점

사전 순으로 정렬을 먼저 한 이유는 max값이 여러 개일 경우에 정렬 없이 코드를 진행해왔다면 코드가 복잡해질 것 같았기 때문이다. 금방 풀었다.