글 읽기 - 출력부분만 살짝 바꿀경우, 시간초과 발생

erik5022 3년 전 0

아래 소스 코드 main 함수에서

option1 로 할 경우에는 시간초과가 발생하고

option2 로 할 경우에는 맞습니다.

option1 로 할 경우 왜 시간초과가 발생할까요? ㅡㅡ;

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

const int MAX = 500000 + 1;

int N;
pair<int, int> connect[MAX];
pair<int, int> answer[MAX];
int cache[MAX];
int cache2[MAX];
bool visited[MAX];
stack<int> s;
vector<int> del;

int LIS(void)
{
    int idx = 0;
    int length = 0;
    cache[idx] = connect[0].second;
    cache2[idx] = connect[0].first;
    answer[0] = { 0, connect[0].first };

    for (int i = 1; i < N; i++) {
        if (cache[idx] < connect[i].second) {
            cache[++idx] = connect[i].second;
            cache2[idx] = connect[i].first;
            answer[i] = { idx, connect[i].first };
        }
        else {
            int idx2 = lower_bound(cache, cache + idx, connect[i].second) - cache;
            del.push_back(cache2[idx2]);
            cache[idx2] = connect[i].second;
            cache2[idx2] = connect[i].first;
            answer[i] = { idx2, connect[i].first };
        }
    }
    return idx + 1;
}

int main(void){

    //freopen("Input.txt", "r", stdin);
    //freopen("Output.txt", "w", stdout);

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        cin >> connect[i].first >> connect[i].second;
        visited[connect[i].first] = true;
    }

    sort(connect, connect + N);

    int result = LIS();
    cout << N - result << "\n";

    

    // option1
    for (int i = 0; i < del.size(); i++) {   
        cout << del[i] << endl;        
    }
    
    // option2    
    int num = result - 1;
    for (int i = N - 1; i >= 0; i--)
        if (answer[i].first == num)
        {
            s.push(answer[i].second);
            num--;
        }

    while (!s.empty())
    {
        visited[s.top()] = false;
        s.pop();
    }

    for (int i = 0; i < MAX; i++)
        if (visited[i])
            cout << i << "\n";
    
    return 0;

}

djm03178 3년 전 1

endl 때문에 그렇습니다.

https://www.acmicpc.net/proble...

1214sw 3년 전 0

감사합니다..도움됐습니다!

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

문제

문제

출처

ICPC

출력부분만 살짝 바꿀경우, 시간초과 발생

erik5022 3년 전 0

djm03178 3년 전 1

1214sw 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말