13414번 수강신청

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

#include <map> : https://hsdevelopment.tistory.com/251

어려웠다.

문제를 읽고, 이건 map을 이용할 수 밖에 없는 느낌을 받았고,

계속 map을 요리하면서(insert, erase의 활용 등등..) 그리고 vector도 요리하면서(unique 등등등...)

풀려고 몇 시간 동안 고민하였으나 결국 풀지 못 했다.

그래서 다른 분의 코드를 참고하였다.

참고하니, 내가 놓치는 부분들이 있었다.

1. map의 insert, count, erase 연산은 느리다. 그래서, 배열 형식으로 Key, Value를 저장해줘야한다.

2. K가 vector v의 v.size()보다 클 경우, 같은 경우, 작은 경우 이렇게 2가지(오타 아님.) 경우로 나누어서 생각했어야 했다.

3. 많은 양의 데이터를 보고, 이건 sort를 사용하지 않는 방법이 있을 것이다 라고 생각하여 sort를 쓰지 않으려고 했다. 그런데 답은 역시나 sort를 써야 했었다.

4. 문제를 풀면서 test 하고 있었는데, 문제의 01234567이 int로 1234567이 출력되는 것이었다. 이것을 그대로 01234567로 출력하려면 string으로 선언해야 하는데, 나는 "어 그냥 1234567로 출력되네"라고만 생각하고 넘어갔었다. string을 떠올렸어야 했다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
// https://www.acmicpc.net/problem/13414
 
map<string, int> m;
 
int K = 0, L = 0;
 
vector<pair<string, int> > v;
 
bool cmp(const pair<string, int> & a, const pair<string, int> & b)
{
    return a.second < b.second;
}
 
int main(void)
{
    string s;
 
    scanf("%d %d", &K, &L);
 
    for (int i = 1; i <= L; i++)
    {
        cin >> s;
 
        m[s] = i; // '= 1'로만 하는 고정 관념을 버리자.
    }
 
    auto itr = m.begin();
 
    while (itr != m.end())
    {
        v.push_back({ itr->first, itr->second });
 
        // 또는 cmp를 사용하지 않으려면, v.push_back({ itr->second, itr->first }); 라고 해도 된다.
 
        ++itr;
    }
 
    sort(v.begin(), v.end(), cmp);
 
    // K가 더 큰 경우, 작은 경우 이렇게 케이스를 나누는 것을 전혀 생각하지 못 했다.
 
    if (K <= v.size())
    {
        for (int i = 0; i < K; i++) cout << v.at(i).first << '\n';
    }
    else
    {
        for (int i = 0; i < v.size(); i++) cout << v.at(i).first << '\n';
    }
 
    return 0;
}