글 읽기 - 시간초과 이유 알 수 있을까요??

skesswswkk 4년 전 0

시간초과가 while()문에서 나는 것 같은데 어떤 반례의 경우에 나는지 궁금합니다!

#include <iostream>
#include <deque>
using namespace std;

int arr[1000 + 5];
deque<int> dq;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	for (int i = 0; i < n; ++i) {
		cin >> arr[i];//5 4 3 2 "1" 6 7 8 9 10
	}

	int cnt = 1;
	for (int i = 0; i < n; ++i) {
		if (cnt == arr[i]) {
			//cout << cnt << endl;
			cnt++;//2
		}
		else {
			if (dq.size() == 0 || dq.back() != cnt) {
				dq.push_back(arr[i]);//5 4 3 2 
			}
			else {
				while (dq.size() > 0) {
					if (cnt == dq.back()) {
						//cout << cnt << endl;
						dq.pop_back();
						cnt++;//6
					}
				}
				if (dq.size() == 0) {
					dq.push_back(arr[i]);
				}
			}
		}
	}

	int size = dq.size();
	for (int i = 0; i < size; ++i) {
		if (cnt != dq.back()) {
			cout << "Sad" << "\n";
			return 0;
		}
		else if (cnt == dq.back()) {
			dq.pop_back();
			cnt++;
		}
	}

	cout << "Nice" << "\n";
}

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

문제

문제

출처

ICPC

시간초과 이유 알 수 있을까요??

skesswswkk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말