[백준/Baekjoon] 13414 수강신청 C++ :: Data structure

 

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

13414번: 수강신청

---

1. Logic

중복을 포함하지 않는다고 했기 때문에 map대신 unordered_map을 사용했다. 그리고 입려이 50만이기 때문에 logN을 시간복잡도로 가지는 map에 비해 O(1)을 가지는 unordered_map을 사용하는게 좋을 것 이라고 생각했따.

 

unordered_map의 key:학번 value:클릭한 순서 로 설정하고 입력은 받은 후 vector<pair<string, int>> 로 설정하여 원소를 넣어주고 오름차순 정렬한 후 ㄱ수강 가능 인원 만큼 출력해 주면 된다.

Out of bounds가 떠서 확인 해봤더니 수강 가능인원보다 적게 신청했을 경우 n만큼 출력 하면 할당된 배열보다 넘어서 참조하기 때문에 Out of bounds가 뜬다. 그래서 n와 temp.size()중 최솟값을 선택 해 줬다.

---

2. Code

#include <bits/stdc++.h>

using namespace std;

int n, m;

unordered_map<string, int> um;

bool cmp(pair<string, int> &a, pair<string, int> &b) {
    return a.second < b.second;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    
    for(int i = 0; i < m; i++) {
        string str;
        cin >> str;
        
        um[str] = i;
    }
    
    vector<pair<string, int>> temp;
    
    for(auto & a : um) {
        temp.push_back(a);
    }
    
    sort(temp.begin(), temp.end(), cmp);
    
    for(int i = 0; i < min(n, (int)temp.size()); i++) {
        cout << temp[i].first << "\n";
    }
}

---

3. Feedback

문제에 나오지 않은 경우의 수도 한번 생각해 보는게 좋을 것 같다. 처음 코드를 짤 때 최소 가능인원보다 적게 신청하는 경우를 생각을 못했었다

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐