글 읽기 - 시간초과ㅠㅠㅠ

sambongdj 6년 전 0

배열을 전부 1씩 뺀 배열을 만든 후 조건에 맞게 수정하면서 n^2정도의 시간복잡도가 나와 시간초과가 뜨는 것 같습니다.

어떻게 푸는 건가요,,ㅠㅠㅠ

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

vector<int> S, res;
vector<bool> fixxed;
int n;

bool satisfy(int k,int p){
    if(S[p]-1<=k&&k<=S[p]+1) return true;
    return false;
}

void solve(){
    fixxed = vector<bool>(n+1,false);
    int k=0;
    int cnt=0;
    bool fg=true;
    for(int i=0;i<n;i++){
        if(S[i]==i+1 && fg==true){ res[i] = i+1; cnt++; }
        else {
            fg=false;
            res[i] = S[i]-1;
            if(res[i]==cnt) { res[i]=n; k=i; }   
        }
    }
    while(1){
        if(satisfy(res[k],k)==true) break;
        for(int i=n-1;i>=0;i--){
            if(fixxed[i]==false&&satisfy(res[k],i)==true){
                swap(res[k],res[i]);
                fixxed[i]=true;
                break;
            }
        }
    }
    for(int i=0;i<n;i++) printf("%d\n",res[i]);
    return;
}   
    
int main(){
    cin >> n;
    S = res = vector<int>(n,0);
    for(int i=0;i<n;i++) scanf("%d",&S[i]);
    solve();
}

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

문제

문제

출처

ICPC

시간초과ㅠㅠㅠ

sambongdj 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말