1-I 시간초과 질문 있습니다.

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

1-I

해결된 질문

작성

298

#include <bits/stdc++.h>

using namespace std;

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

    int N, M;

    cin >> N >> M;

    map<int, string> book;
    vector<string> answer;

    for (int i = 1; i <= N; i++)
    {
        string pokemon;

        cin >> pokemon;

        book[i] = pokemon;
    }

    for (int i = 0; i < M; i++)
    {
        string question;

        cin >> question;

        for (auto const &[k, v] : book)
        {
            if (to_string(k) == question || question == v)
            {
                answer.push_back(isalpha(question[0]) ? to_string(k) : v);
                break;
            }
        }
    }

    for (auto str : answer)
        cout << str << '\n';

    return 0;
}

해당 코드에서 시간 초과가 나는데

        for (auto const &[k, v] : book)
        {
            if (to_string(k) == question || question == v)
            {
                answer.push_back(isalpha(question[0]) ? to_string(k) : v);
                break;
            }
        }

아마 이 부분에서 시간 초과가 나리라 생각합니다.

O(NlogN) 일거 같은데

답안과 달리 map 1개와 find 만 써서 풀 수는 없는걸까요?

왜 시간초과가 나는지 이해가 잘 안갑니다.

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 123님 ㅎㅎ

       for (auto const &[k, v] : book)
        {
            if (to_string(k) == question || question == v)
            {
                answer.push_back(isalpha(question[0]) ? to_string(k) : v);
                break;
            }
        }

이부분이요 map에 있는 전체적인 요소들을 탐색하는 것이죠? 이부분은 O(logN)이 아니라 O(N)입니다.

map은 레드블랙트리기반으로 균형잡힌 트리로써 어떠한 요소를 이 map을 이용해서 탐색할 때는 O(logN)이 걸립니다.

가령 이런식의 코드에서 mp[1] map에서 1이라는 녀석을 찾는 부분은 O(logN)의 시간복잡도를 가집니다.

#include <bits/stdc++.h> 

using namespace std;   
map<int, int> mp;
int main() { 
	mp[1] = 0;
	if(mp[1] == 0){
		cout << 1 << '\n';
	}
    return 0;
}

그러나 123님의 코드는 map에 있는 모든 요소들을 순회하기 때문에 O(logN)이 아니라 O(N)의 시간복잡도를 가진다고 볼 수 있습니다. 따라서 시간초과가 나는 것 같습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

qlghwp123

질문자

map 이 RB 트리라서 당연하게도 순회도 O(logN) 이라 생각했는데 제가 큰 착각을 했네요.

감사합니다!

인프런 커뮤니티 질문&답변

1-I 시간초과 질문 있습니다.