문제 푼 날짜 : 2021-11-01

문제

문제 링크 : https://www.acmicpc.net/problem/13414

접근 및 풀이

처음엔 입력값을 vector에 넣어주다가, find 함수를 이용하여 vector에 존재하는 값이 들어오면 기존의 값을 erase해주는 방식으로 구현했다. 하지만, 시간초과가 떴다. (웬만하면 find는 쓰면 안될 것 같다...)

모든 입력값을 vector에 넣어준 다음, vector의 마지막 값부터 탐색하며 set을 이용하여 이미 넣어준 값을 체크해주었다.

코드(시간초과)

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int K, L;
    cin >> K >> L;
    
    vector<string> v;
    
    for (int i = 0; i < L; i++) {
        string str;
        cin >> str;
        
        auto it = find(v.begin(), v.end(), str);
        if (it != v.end()) {
            v.erase(it);
        }
        v.push_back(str);
    }
    for (int i = 0; i < K; i++) {
        cout << v[i] << '\n';
    }
    return 0;
}

코드(통과)

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int K, L;
    cin >> K >> L;
    
    vector<string> v, ret;
    set<string> st;
    
    for (int i = 0; i < L; i++) {
        string str;
        cin >> str;
        v.push_back(str);
    }
    for (int i = v.size() - 1; i >= 0; i--) {
        if (st.find(v[i]) == st.end()) {
            st.insert(v[i]);
            ret.push_back(v[i]);
        }
    }
    for (int i = ret.size() - 1; i >= 0 && K > 0; i--, K--) {
        cout << ret[i] << '\n';
    }
    return 0;
}

결과

피드백

문제를 풀 때, 여러가지 STL을 이용하는 연습을 하자.