글 읽기 - 시간초과가 왜 나는지 모르겠습니다.

sg1774 5년 전 0

이게 왜 시간초과가 날까요? 반복 횟수가 100만을 안넘을텐데... 아무리 봐도 remove 때문에 그런 것 같은데 remove 함수의 시간 복잡도를 알려주실 분 있으면 감사하겠습니다!

#include <bits/stdc++.h>

using namespace std;
list<int> l;
int main()
{
    int z,x;                //z=k,x=l
    scanf("%d %d",&z,&x);
    for(int i=0;i<x;i++){
        int a;
        scanf("%d",&a);
        l.remove(a);        //만약 이미 원소가 있다면 앞의 원소를 지움
        l.push_back(a);     //원소를 넣어줌
    }
    list<int>::iterator it;
    l.resize(z);            //남아있는 원소의 수가 z개가 되도록 뒤의 원소들을 없애줌
    for(it=l.begin();it!=l.end();it++) printf("%08d\n",*it);
    return 0;
}

sg1774 5년 전 0

맵으로는 이렇게 풀었는데 이건 런타임 에러가 나네요ㅠㅠ

#include <bits/stdc++.h>

using namespace std;
map <int,int> m;
int a[500000];
int main()
{
    int z,x,l=0;
    scanf("%d %d",&z,&x);
    for(int i=0;i<x;i++){
        scanf("%d",&a[i]);
        m[a[i]]=i;
    }
    for(int i=0;l<z;i++){
        if(m[a[i]]==i){
            printf("%d\n",a[i]);
            l++;
        }
    }
    return 0;
}