글 읽기 - c++ 트리 시간 초과 이유가 뭘까요?(주석 있음)

cyj89317 2년 전 0

아래 코드가 시간 초과 나서, 전위와 중위순회를 이용해 후위순회를 출력하는 방법으로 다시 풀었더니 맞았습니다.

그런데 시간 초과가 나는 이유를 잘 모르겠습니다.

아래 코드는, 입력에 따라 맵으로 트리를 만들고 후위순회로 출력해 줍니다.

트리에 노드 입력은 평균 O(logN)이고, 최악의 경우 O(N)이라고 알고 있습니다.

따라서 복잡도가 최악에 O(N^2)라고 생각했는데, 틀린 부분이 어디일까요?

감사합니다ㅜㅜ

#include <bits/stdc++.h>

using namespace std;

map<int, pair<int, int> > tree;

/*
후위순회 출력
*/
void postorder(int now){
    if( tree[now].first != 0 ) postorder(tree[now].first);
    if( tree[now].second != 0 ) postorder(tree[now].second);
    cout << now << '\n';
}

/*
k를 알맞은 부모 r의 자식으로 넣기
*/
void addNode(int r, int k){
    if( k < r ){
        // k가 r보다 작은데 r의 왼쪽 자식이 있다면 왼쪽 자식을 탐색
        if( tree[r].first ) addNode(tree[r].first, k);
        
        // k가 r보다 작은데 r의 왼쪽 자식이 없으면 k를 왼쪽 자식으로 설정
        else{
            tree[r].first = k;
            return;
        }
    }
    else{
        // k가 r보다 큰데 r의 오른쪽 자식이 있다면 오른쪽 자식을 탐색
        if( tree[r].second ) addNode(tree[r].second, k);
        
        // k가 r보다 큰데 r의 오른쪽 자식이 없으면 k를 오른쪽 자식으로 설정
        else{
            tree[r].second = k;
            return;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    vector<int> v;
    int a, root = 0;
    while( cin >> a ){
        tree[a] = make_pair(0, 0);    // 노드 생성
        if( root == 0 ) root = a;    // 루트가 비었으면 루트 설정
        else addNode(root, a);    // 루트가 있으면 노드를 트리에 넣기
    }
    postorder(root);    // 트리를 후위순회로 출력
}

bamgoesn 2년 전 1

위 코드는 BST(이진검색트리)를 사실살 그대로 구현하고 있으나 각 노드를 map에 저장하고 있습니다.

map은 원소를 삽입, 삭제, 탐색하는 과정에서 O(logN)이 걸립니다. 이때문에 실제 시간복잡도는 질문자님이 예상하신 것에 logN이 붙어 O(N^2 logN)이 됩니다.

BST에 노드를 삽입할 때 각 노드의 값을 확인하는 과정이 O(1)이 아니라 O(logN)이 되기 때문입니다. 이때문에 시간초과가 나는 것으로 보입니다.

cyj89317 2년 전 0

아 제가 그걸 생각 못했네요!! 맵 자체가 O(logN)이었죠

설명 정말 감사드립니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 트리 시간 초과 이유가 뭘까요?(주석 있음)

cyj89317 2년 전 0

bamgoesn 2년 전 1

cyj89317 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말