[BOJ 1302] 베스트셀러

문제 : 김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.
오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

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

1302번: 베스트셀러

문제 분석

• 문제를 보자마자 팔린 권수만 입력한다면 최댓값을 구하는 문제이기 때문에 금방 풀텐데라는 생각이 들었다.
• 그렇다면 팔린 권수를 알아내는 코드를 삽입하면 되겠구나 라는 생각을 했다.
• 고민하던 도중 <pair>를 써서 팔린 권수와 제목을 함께 갖고 있는 stl을 사용해 문제를 풀고자 했다.
• <map>을 사용하면 금방 풀었겠으나 풀 때 당시에는 <map>을 잘 알지 못해 생각조차 못하고 있었다.

주의 사항

• 책제목은 알파벳 소문자로만 이뤄져 있다.
• 가장 많이 팔린 책이 여러 권인 경우 사전 순으로 가장 앞서는 제목을 출력한다.

#include <iostream>
#include <vector>
using namespace std;
int n,m;
vector<pair<string,int>>title;//팔린 책 제목, 팔린 권수를 저장하는 벡터
bool exist; //입력값이 벡터에 존재하는지에 대한 변수
string input,result;
int main(){
    cin>>n;
    while(n--){
        cin>>input;
        exist = false;//변수 초기화
        for(auto & i : title){//선형 탐색
            if(input==i.first) {// 팔린 책 리스트에 존재하면 
                exist = true;
                i.second +=1;//팔린 권수 +1
            }
        }
        if(!exist){//존재하지 않으면
            title.push_back(make_pair(input,1));//새로운 책 제목 리스트에 입력
        }
    }
    //m은 베스트셀러의 팔린 권수
    for(auto & i : title){
        if(i.second>m){//m보다 크면
            m = i.second;//새로운 m
            result = i.first;
        }
        else if(i.second==m){//만약 m과 같은 값을 가지면
            if(i.first<result) result = i.first;//사전순으로 앞서는 책이 결과값
        }
    }
    cout<<result<<endl;
    return 0;
}

시간복잡도 계산

• n번 반복하는 while문
• 최악의 경우 1+2+...+n번 반복하는 범위기반 for문
• n번 반복하는 범위기반 for문
  ☞ O(n^2)

느낀점

• "문제가 좀만 바뀌면 참 풀기 쉬울텐데..."라는 생각이 들때가 종종 있다. 그럴때는 내가 원하는 대로 바꾸는 코드를 고민하는 것도 큰 도움이 될것 이라는 생각이 든다.
• 다시 문제를 봐보니 코드가 꽤 비효율적이다.아무래도 <vector>의 선형탐색을 사용하다보니  시간이 오래걸린것 같다.
• <map>을 이용했다면 훨씬 효율적으로 풀 수 있었을 것이다. 조만간 <map>을 이용한 코드로 재제출을 해봐야 겠다.