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

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

1302번: 베스트셀러

어떤 문제인가?

요구사항은 간단하다.

1. 책의 개수 N이 주어진다 -> N번 입력을 받는다.

2. 입력받은 책의 이름과 판매 수량을 저장한다.

3. 가장 많이 팔린 책의 제목을 출력한다.

 

 

접근 방법

먼저 책의 이름과 판매 수량을 저장할 자료구조가 필요했다.

vector<pair<string ,int>> book;

큰 고민 없이 pair와 vector를 사용해 책의 이름, 판매수량을 저장할 수 있었다.

 

string b;
cin >> b;
vector<pair<string ,int>>::iterator iter;
bool contain= false;

for(iter = book.begin(); iter != book.end();iter++){
    if(iter->first == b){
        iter->second++;
        contain= true;
        break;
    }
}

그다음, 책의 이름을 입력받는다. book을 탐색할 iterator와 book안에 입력받은 책의 이름이 존재 여부를 판단할 contain을 선언해준다.

 

그리고 book의 시작과 끝을 순회하며 만약, iter->fisrt가 입력받은 책의 이름과 같다(이미 팔린 적이 있음)면 iter->second(판매수량)을 1 증가시켜주고 contain을 true로 설정한 후 탈출한다.

 

if(!contain){
    book.push_back(pair<string,int>(b,1));
}

만약 for문이 끝났을 때 contain이 false라는 뜻은 전에 팔린 적이 없고, 처음 팔린 것이라는 뜻이다.

따라서 book에 책의 이름과 1의 pair를 추가해준다.

 

 

sort(book.begin(),book.end(), compare) 

이제 sort함수를 통해 book을 문제의 요구사항대로 출력하기 쉽게 정렬해야 한다.

문제의 요구사항은 가장 많이 팔린 책의 제목을 출력하고, 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞에 있는 책의 제목을 출력하는 것이었다.

따라서 정렬 조건은

1. pair의 second(판매수량) 오름차순

2. 만약 pair의 second(판매수량) 동일 -> pair의 first(책의 이름) 사전 순 정렬

 

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

    return a.second > b.second;
}

따라서 compare함수는 이렇게 작성할 수 있다!

 

이렇게 정렬을 마친 후에는 판매수량의 개수가 가장 높고 사전 순으로도 가장 빠른 책이 book의 맨 앞에 존재할 것이다.

cout << book.begin()->first;

 출력만 해주면 끝!

 

무엇이 어려웠나?

모두 원래 알고 있던 지식으로도 충분히 해결 가능해서 어렵다고 느껴지진 않았다.

실수했던 것은 compare함수를 작성할 때 생각 없이 밑에 처럼 부등호를 잘못 작성했다.

그리고 맞왜틀을 시전 하다가 발견하고 약간 뻘쭘했다...ㅋ

if(a.second == b.second){
    return a.first > b.first;
}

 

배운 점

지식적인 부분에서 특별하게 배운 것은 없었다.

하지만 아무리 다 알고 있고 쉬워 보이는 문제라도 꼼꼼하게 실수 없이 작성해야 하는 것의 중요성을 다시 한번 느꼈다.

시간 복잡도

내 풀이의 경우

일단, 입력한 n번만큼 for문을 실행하고, 그 안에서 존재 여부를 판단하는 for문이 실행된다.

이때 만약 입력으로 모두 다른 이름의 책이 입력된다면 book의 탐색이(for문)이 또 n번만큼 실행될 것이다.

따라서 최악의 경우 O(N^2)의 시간 복잡도를 갖는다.

그렇게 좋은 코드는 아니다.

사실 find함수를 사용하면 간단해지겠지만, 문제를 풀 때의 나는 의식의 흐름대로 풀다 보니 이렇게 풀었고 통과했기 때문에 따로 수정해서 다시 제출해보지 않았다.

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/1302.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.