백준 1713 후보 추천하기 (C++)

안유태·2023년 12월 6일
0

알고리즘

목록 보기
196/239

1713번: 후보 추천하기

주어진 조건을 직접 구현하는 문제이다. 맵을 사용하였으며 키에는 추천받은 학생 번호를, 값에는 추천수와 값이 위치한 인덱스를 저장해주었다. 현재 값이 맵에 이미 있을 경우 그 값의 추천수를 +1해주고, 없다면 새로 추가해주었다. 추가해줄 때 만약 맵의 크기가 N과 같다면 기존에 있던 값들 중 가장 낮은 추천수, 혹은 오래된 값을 찾아 제거해주고 새로운 값을 추가해주었다. 후에 맵에 있는 값들을 차례대로 출력해주었다. 어렵지 않게 풀 수 있었던 문제였다.



#include <iostream>
#include <map>

using namespace std;

int N, r;
int A[1000];
map<int, pair<int, int>> m;

void solution() {
    for (int i = 0; i < r; i++) {
        if (m.find(A[i]) == m.end()) {
            if (m.size() == N) {
                int idx = m.begin()->first;
                pair<int, int> value = m.begin()->second;

                for (auto elem : m) {
                    if (elem.second < value) {
                        idx = elem.first;
                        value = elem.second;
                    }
                }
                m.erase(idx);
            }

            m[A[i]].first = 1;
            m[A[i]].second = i;
        }
        else {
            m[A[i]].first++;
        }
    }

    for (auto elem : m) {
        cout << elem.first << " ";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;
    cin >> r;

    for (int i = 0; i < r; i++) {
        cin >> A[i];
    }

    solution();

    return 0;
}
profile
공부하는 개발자

0개의 댓글