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

주말이다~~

그래서 블로그로 출근하기 힘들었다...

그래도 어떻게 앉아서 이렇게 쓰고 있다(쓰담쓰담).

오늘도 문제를 골라볼까~~

 

문제

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

1302번: 베스트셀러

 

음... 이번 문제도 배열에 n개만큼 입력받아서 넣어주고, 배열 안에 있는 책의 제목들을 비교해 보면서 가장 많이 팔린 책의 이름을 출력할 변수에 저장하면 될 것 같다.

 

 

그런데!! 코드를 한참짜다가 이상함을 발견했다.

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 
가장 앞서는 제목을 출력한다.

아 ㅋㅋㅋ나 진짜 바본가?? 출력 조건을 잘못 봤다... 제목 하나만 출력해 주면 된다는 거였는데, 나는 그 여러 개의 책 제목들을 사전 순으로 출력하라는 줄 알았다(잘 좀 읽자...). 그래서 vector에 그 제목들 넣고 난리부렸는데 ㅠㅠ

어쩐지 뭔가 이상하더라 ㅋㅋㅋ 삽질을 너무 많이 했다.

 

//틀린 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

string sell[1000];	//책을 담은 배열
string max_name;	//가장 많이 팔린 책
int max_num = 0;	//가장 많이 팔린 수

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> sell[i];
	}
	sort(sell, sell + n);//사전 순으로 정렬

	if (n == 1) {	//팔린 책이 한 개면 그대로 넣어주기
		max_name = sell[0];
	}

	for (int i = 0; i < n-1; i++) {
		int sum = 1;
		for (int j = i+1; j < n; j++) {
			if (sell[i] == sell[j]) {
				sum++;
				//이 전에 사전 순으로 정렬해주었기 때문에 개수가 같을 경우를 따로 만들지 않아도 앞에 있는 것이 출력
				if (sum > max_num) {
					max_num = sum;
					max_name = sell[i];
				}
			}
		}
		if (sell[i] == sell[i+1]) {//그 전에 비교한 책이랑 같은 이름이면 넘어가기
			continue;
		}
	}


	cout << max_name << endl;

	

	return 0;
}

 

이렇게 짰는데... 분명히 이번에도 예제는 다 맞았는데... 왜 ㅠㅠ 틀렸을까?? 모르겠다...(속상)

 

 

 

#include <iostream>
#include<map>
using namespace std;

int main()
{
	map<string, int> book;
	int len, max = 0;
	string res,str;
	cin >> len;

	for (int i = 0; i < len; i++)
	{
		cin >> str;
		book[str]++; //책의 갯수 측정
	}

	for (auto curBook : book)
	{
		if (curBook.second >= max) //가장 큰 책의 갯수를 찾음
		{
			max = curBook.second;
			res = curBook.first;
		}
	}
	cout << res;
}
출처: https://ohsol.tistory.com/entry/백준-1302-베스트셀러-C풀이 [오솔의 블로그:티스토리]

컨테이너인 map을 사용하면 아주 빠르고 간편하게 풀 수 있는 문제라고 하신다.

map..? 그게 뭐지??

 

map이란?: 키(key)와 자료(value)를 저장, 키를 이용해 원하는 자료를 빠르게 찾을 수 있도록 하는 자료구조이다.

c++ 에선 #include <map>을 통하여 사용할 수 있다.

map의 특징: 전체 조회를 통해 key를 기준으로 오름차순으로 자동 정렬된 것을 확인, 중복 저장은 불가

(이는 균형 이진 검색 트리를 이용하기 때문에 발생하는 특징)

 

 

 

 

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;

	map<string, int> m;
	while (n--)
	{
		string str;
		cin >> str;

		if (m.find(str) == m.end())
			m.insert({ str, 1 });
		else
			m[str]++;
	}

	int max = 0;
	string res;
	for (auto& i : m)
		if (i.second > max)
			res = i.first, max = i.second;

	cout << res;
	return 0;
}

출처:https://velog.io/@beclever/C-%EB%B0%B1%EC%A4%80-1302%EB%B2%88-%EB%B9%97%EB%AC%BC

map을 이용하면 쉽게 해결할 수 있다고 하셨다.

입력을 받으면 맵의 내부에 해당 Key가 존재하는지 확인하고,

 

만약 존재하지 않는다면 value를 1로 해서 삽입

Key가 존재한다면 대응되는 value를 1 증가

 

C++ 레퍼런스에  std::map은 내부적으로 정렬이 된다. 따라서 std::map에 입력을 모두 마치면, 처음부터 이동하면서 최댓값을 찾으면 된다. 그러면 자연스레 사전 순으로 가장 앞서는 제목을 찾을 수 있다.

 

 

 

다 map을 쓰셔서 map을 안 쓴 것도 찾아보았다.

#include <stdio.h>  // 베스트셀러
#include <string.h>
#include <stdlib.h>

typedef struct
{
	char name[51];
	int cnt;
}book;

int compare(void* a, void* b)
{
	if (strcmp(a, b) > 0)
		return 1;
	else
		return -1;
}

int main()
{
	int n;
	scanf("%d", &n);

	book b[1000];

	char str[51];
	int total = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%s", str);

		b[i].cnt = 0;
		if (i == 0)
		{
			strcpy(b[i].name, str);
			total++;
		}
		else
		{
			// 같은 단어가 존재하면 해당 cnt 증가
			int j = 0, flag = 0;
			while (j < i)
			{
				if (strcmp(str, b[j].name) == 0)
				{
					flag = 1;
					b[j].cnt++;
					break;
				}
				j++;
			}
			// 처음 나온 단어의 경우 새로 추가 
			if (flag == 0)
			{
				strcpy(b[i].name, str);
				total++;
			}
		}
	}

	// 문자열 정렬(개수가 같을 때의 경우 대비)
	qsort(b, total, sizeof(b[0]), compare);

	// 가장 많이 나온 단어 찾기
	int idx, ans = 0, max = -1;
	for (idx = 0; idx < total; idx++)
	{
		if (b[idx].cnt > max)
		{
			max = b[idx].cnt;
			ans = idx;
		}
	}

	printf("%s", b[ans].name);

	return 0;
}
출처: https://kthyeong.tistory.com/27

이 분은 구조체 배열을 통해서 단어를 담을 공간과 카운트를 해줄 변수를 생성해주셨다. 단어를 입력 받으며 이미 저장한 단어의 경우 해당 단어가 위치한 구조체의 cnt를 증가시키고 처음 입력 받은 경우에는 새로운 구조체 배열에 이름을 추가해주셨다. 책 이름들은 퀵정렬을 이용해 오름차순으로 정렬 후 최대 cnt 값(가장 많이 저장된 책)을 찾아주었다.

 

 

내가 한거는 고쳐서 할 수는 없나 라는 생각이 들어서 https://jaimemin.tistory.com/886 여기를 참고하여 고쳐보았다.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

vector<string> sell;	//책을 담은 배열
string max_name;	//가장 많이 팔린 책
int max_num = 0;	//가장 많이 팔린 수

int main() {
	int n;
	int sum = 0;	//비교할 수
	string name;	//비교할 책
	cin >> n;
	for (int i = 0; i < n; i++) {
		string a;
		cin >> a;
		sell.push_back(a);
	}
	sort(sell.begin(), sell.end());//사전 순으로 정렬

	name = sell[0];
	for (int i = 0; i < n; i++) {
		if (sell[i] == name) {
			sum++;
		}
		else{
			if (sum > max_num) {
				max_num = sum;
				max_name = name;
			}
			name = sell[i];
			sum = 1;
		}
	}

	if (sum > max_num) {
		max_name = name;
	}
	cout << max_name << endl;

	

	return 0;
}

 

오예~~ 감사합니다.

 

 

 

다음에는 꼭!!

맞춰야지~~