[BOJ / C++] 여우는 어떻게 울지? (실버3 - 문자열)

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

 

1. 코드

#include <bits/stdc++.h>
using namespace std;

vector<string> split(string& s, string& sep) {
    vector<string> ret;
    int pos = 0;
    while (pos < s.size()) {
        int nxt_pos = s.find(sep, pos);
        if (nxt_pos == -1) nxt_pos = s.size();
        if (nxt_pos - pos > 0) {
            ret.push_back(s.substr(pos, nxt_pos - pos));
        }
        pos = nxt_pos + sep.size();
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;
    cin.ignore();

    while (t--) {
        string record;
        getline(cin, record);

        string sep = " ";
        vector<string> recordLst = split(record, sep);
        
        vector<string> sounds;
        while (true) {
            string s;
            getline(cin, s);
            
            if (s == "what does the fox say?") break;
            
            vector<string> lst = split(s, sep);

            sounds.push_back(lst[2]);
        }

        for (string word : recordLst) {
            auto it = find(sounds.begin(), sounds.end(), word);
            if (it == sounds.end()) {
                cout << word << " ";
            }
        }
    }
}

 

 

2. 시간복잡도

단어 개수는 100개, 단어 글자는 100개, 동물 개수도 100개이다. 최악의 경우 모두 순회하면서 비교해야한다.

O(100 * 100 * 100) = O(1,000,000) < 10^8이므로 시간내 통과 가능하다.

만약 단어 개수나 동물개수가 더 많았다면 vector가 아닌 set이나 unordered_set을 써서 시간복잡도를 낮춰야했다.

 

 

3. 분석

• split을 먼저 정확하게 구현하는 것이 필요하다.
• split을 이용해 동물 울음소리를 따로 저장해두고 녹음사운드와 비교해서 동물 울음소리들은 제외하고 출력하면 된다.