백준(BOJ) 1302번 베스트셀러

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

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

입력

첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

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

나의풀이 :

pair<string,int> vector에 책이름과 판매수를 적고 판매수를 기준으로 오름차순 정렬한다.

정렬된 list에서 제일 가장 많이 팔린 중복된 책들만 모아서 다시 sortagain으로 사전 정렬 한다.

sortagain에서 제일 앞에있는 사전 순으로 정렬된 책을 출력한다.

코드(C++)

bool compare(const pair<string, int>&a, const pair<string, int>&b)

{

return a.second < b.second;

}

vector<pair<string, int>> list;

int N;

void check(string s) // 이미 리스트에 s가 있다면 팔린 책 수에 1 더해줌

{

for (int i = 0; i < list.size(); ++i)

{

if (s == list[i].first)

list[i].second++;

}

list.push_back(make_pair(s, 1)); // 리스트에 없다면 s를 등록하고 팔린 책 수 1 등록

}

int samekey(const vector<pair<string, int>>& list) 

{

//정렬된 list에서 mostSell는 제일 잘 팔린 책의 수

int mostSell = list[list.size() - 1].second;

for (int i = list.size() - 2; i > 0; --i)

if (mostSell != list[i].second)  

{

return i; // 똑같이 팔린 책 바로 앞 index 반환

}

return -1; // 모두 다 똑같이 팔렸다면 -1 반환

}

int main()

{

cin >> N;

for (int i = 0; i < N; ++i)

{

string s;

cin >> s;

check(s); // list에 있나 확인

}

int bestsell = 0;

sort(list.begin(), list.end(), compare);  // list에 팔린수 기준 정렬

int key = samekey(list);  //가장 많이 팔린 수가 중복일때

vector<string> sortagain;

for (int i = key + 1; i < list.size(); ++i)

{

sortagain.push_back(list[i].first);   //가장 많이 팔린 책의 이름들을 넣어줌

}

sort(sortagain.begin(), sortagain.end()); // 사전순으로 정렬

cout << sortagain[0] << endl; // 제일 앞에 있는 책 출력 

return 0;

}