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

map library 사용 연습을 위해 푼 문제다.

sort를 이용한 실패 코드

#include <iostream>
#include <map> // hash
#include <vector> // map 정렬
#include <utility> // pair
#include <algorithm> // sort
#include <string>

using namespace std;

bool comp(pair<string, int> a, pair<string, int> b){
  if(a.second > b.second){
    return a > b;
  }
  return a < b;
}

int main(){
  int n;
  string name;
  map<string, int> m; // key 값 오름차순 정렬

  cin >> n;

  for(int i = 0; i < n; i++){
    cin >> name; // 이름 받아오기
    m[name]++; // 수 세기
  }

  vector<pair<string, int>> v(m.begin(), m.end()); // map -> vector
  sort(v.begin(), v.end(), comp);

  // 확인용 map 전체 출력
  for(auto iter : v){
    cout << iter.first << iter.second << " ";
  }

  cout << v[0].first;

  return 0;
}

원래 위와 같이 comp를 사용해서 sort를 시켜 쉽게 값을 얻어내려고 했는데 정렬이 생각만큼 잘 안되었다...

10
dc
zxo
abd
pa
ccc
dc
sad
zxcvdq
qteq
abd

위와 같은 반례에서 정답은 abd가 나와야하지만 나는 계속 ccc가 나옴

ccc1 pa1 dc2 abd2 qteq1 sad1 zxcvdq1 zxo1

확인해보니 위와같이 게속 정렬이 이루어지고 있었다... 두둥 value 값이 더 크면 앞으로 보내라고만 지시했는데 뭐가 문제일까?

아무튼 그래서 소스코드를 수정했다.

풀이 코드

#include <iostream>
#include <map> // hash
#include <string>

using namespace std;

int main(){
  int n;
  int maxNum = 0;
  string name;
  map<string, int> m; // key 값 오름차순 정렬

  cin >> n;

  for(int i = 0; i < n; i++){
    cin >> name; // 이름 받아오기
    m[name]++; // 수 세기
    maxNum = max(maxNum, m[name]);
  }

  for(auto iter : m){
    if(iter.second == maxNum){
      cout << iter.first;
      return 0;
    }
  }

  return 0;
}

그냥 계속 책의 수를 세면서 가장 많은 책의 수(maxNum)를 세어준다.
그리고 map의 경우는 key값을 오름차순으로 가지고 있기 때문에 항상 알파벳순으로 가장 빠른 이름이 앞에 온다. (hash map)
때문에 그냥 처음부터 쭉 찾으며 maxNum이 value인 책의 이름을 출력해주면 된다.