[BOJ/C++] 1713: 후보 추천하기

🥈 Silver 1

✏️ 1차 솔루션

• {게시시간, 사진 번호,사진 추천 횟수} 한쌍으로 저장해서 사진 추천횟수 내림차순, 게시시간 오름차순 정렬을 원칙으로 저장
• 사진 게시 여부 bool로 표시

1. 게시된 사진이라면 추천횟수만 증가
2. 게시된 사진이 아닐경우
   1) 사진 틀이 남아있을 경우에는 해당 사진 push
   2) 사진 틀이 꽉 찼을 경우, 사진 추천횟수 내림차순, 게시시간 오름차순으로 정렬하면 바꿔야할 사진이 vector 첫번째 원소로 정렬되기 때문에 첫번째 원소를 새로운 사진으로 변경
   ➡️ 이때 원래 있던 사진의 게시 여부는 false, 새로운 사진 게시 여부는 true 로 변경
3. 최종적인 사진들은 사진 번호 오름차순 정렬해서 출력

🚨 1차 trouble

틀렸다고 뜨는데 배열을 저장하는 방법에 있어서 struct 와 vector 를 적절하게 사용한 것인지 잘 모르겠음
빈번한 sort 도 비효율적인 것 같음

✏️ 최종 솔루션

⭐️ struct 대신 vector pair 활용 ➡️ 이 방법 사용하면 추천횟수와 게시시간을 따로 떼어서 비교할 필요가 없고 이 둘을 하나의 set로 묶어서 비교 가능해 효율적

• map<사진번호,pair<추천횟수,게시시간>> 로 저장
  ❗️ 추천수가 작으면서 게시기간도 오래된 사진은 현재 사진의 pair<추천횟수,게시시간> 과 for 문으로 모든 map 들의 pair 를 통채로 비교해 탐색
• 사진을 지울 때는 map 의 erase 사용

📌 self feedback

sort 를 사용해서 그때마다 정렬해주고 매번 1번 인덱스의 사진을 교환해주는 것이 아니라 필요할 때마다 for 문으로 최소 횟수 사진을 찾아서 갱신하는 방법이 더 나음 ➡️ 전체 개수가 작기 때문에 가능

✏️ 최종 code

#include <iostream>
#include <map>

using namespace std;

int main() {
    int n,m;
    cin >> n;
    cin >> m;

    map<int,pair<int, int>> photo;  //사진틀에 있는 사진: map<사진번호,추천횟수,게시시간>

    for(int i=0;i<m;i++) {
        int idx;
        cin >> idx;

        // 아직 사진 틀에 없는 사진일 경우
        if (photo.find(idx)==photo.end()) {
            // 사진 틀에 공간 있을 경우
            if (photo.size()<n) {
                photo[idx].first=1;
                photo[idx].second=i;
            }
            else {
                pair<int,int> v;
                int num=photo.begin()->first;   // 사진틀 첫번째 사진 번호 가져오기
                v=photo.begin()->second;    //사진틀 <추천횟수,게시시간> 세트 가져오기

                // 추천횟수가 작은 사진 탐색
                for (auto it:photo) {
                    // 추천횟수가 작은 사진 찾으면 최소 사진 번호, 세트를 갱신하면서 탐색
                    if (it.second<v) {
                        num=it.first;
                        v=it.second;
                    }
                }

                // 최종적으로 지울 사진 지우고 새로운 사진으로 세팅
                photo.erase(num);
                photo[idx].first=1;
                photo[idx].second=i;
            }
        }
        // 이미 사진틀에 있는 사진일 경우
        else photo[idx].first++;
    }

    for (auto it:photo) {
        cout << it.first << " ";
    }
}