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

문제설명

input 1 : 책의 수(n)
input 2~n+1 : 책
2~n+1까지의 책 중 가장 많이 입력된 책을 출력하고, 동일한 갯수이면 사전순으로 더 앞에 오는 책을 출력한다.

풀이방법

여러가지 풀이방법을 생각해보았다.

1. python의 dictionary 사용
   
2. c++의 vector와 pair 사용
   

먼저, 처음 2번으로 풀었을 때의 코드는 다음과 같다.

소스코드 1

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

int main(){
  int n;
  int max_count = -1;
  string max_book_title;
  vector<pair<string, int> > books;
  cin >> n;
  string s;
  for(int i=0; i<n; i++){
    cin >> s;
    bool flag = true;
    for(int j=0; j<books.size(); j++){
      if(books[j].first == s){
        flag = false;
        books[j].second = books[j].second+=1;
      }
    }
    if(flag) books.push_back(make_pair(s, 1)); 
  }
  for(auto i : books){
    if(max_count < i.second){
      max_count = i.second;
      max_book_title = i.first;
    }   
    else if(max_count == i.second){
      if(max_book_title > i.first){
        max_book_title = i.first;
      }
    }
  }
  cout << max_book_title;
}

맞는 코드이긴 하지만, 맘에 들지 않는다.
python으로는 dictionary, c++에서는 map을 활용하면 더 간단하게 구현할 수 있더라.
오랜만에 C++ STL을 사용하려니 vector와 pair밖에 기억이 안났다..

그러면 map 사용법부터 다시 익혀보자.
About Map

map을 활용한 소스코드는 아래와 같다

소스코드 2

#include <iostream>
#include <map>
#include <cstring>

using namespace std;

int main(){
  int n, max_book_count=0; string s;
  map<string, int> m;
  cin >> n;

  for(int i=0; i<n; i++){
    cin >> s;
    m[s]++;
  }
  
  for(auto i : m){
    max_book_count = max_book_count < i.second ? i.second : max_book_count;
  }
  for(auto i : m){
    if(i.second == max_book_count){
      cout << i.first;
      break;
    } 
  }
}