글 읽기 - 이거 시간복잡도 nlogn 아닌가요? 왜 시간초과인지 모르겠습니다.

hy01n 2년 전 0

처음에 map이랑 set이랑 같은원리인줄 모르고 map이랑 set으로 나눠서 풀다가 시간초과 나길래 혹시나 싶어서 map으로만 구현했습니다.
입력 받아주면서 map에 값 넣어주고 cnt 증가시키면서 정렬되어있는 map에 index update시켜주면... nlogn 아닌가요?
어디서 nlogn이 넘어가는 시간복잡도가 생겨서 시간초과가 나오는지 모르겠습니다.

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    // set<int> s;
    int arr[n];
    map<int,int> m;
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
        // s.insert(arr[i]);
        m[arr[i]] = 0;
    }
    int cnt=0;
    for(map<int,int>::iterator iter=m.begin();iter!=m.end();iter++){
        iter->second = cnt;
        cnt++;
    }
    for(int i=0;i<n;i++){
        int k = arr[i];
        printf("%d ", m[k]);
    }
    return 0;
}

Green55 2년 전 1

set,map은 상수가 매우 큰 편이기 때문에 n=100만 정도가 되면 nlogn이 시간초과가 되어도 이상하지 않습니다.

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

문제

문제

출처

ICPC

이거 시간복잡도 nlogn 아닌가요? 왜 시간초과인지 모르겠습니다.

hy01n 2년 전 0

Green55 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말