글 읽기 - 시간초과 관련 질문드립니다.

legendmic2 4년 전 0

이 문제는 스택을 사용해서 맞췄긴 했습니다만,,,

처음에 풀었던 방법이 시간초과가 떴는데 어떤 부분때문인가 궁금해서 질문드립니다.

저대로 하면 O(n^2)이긴 하지만 for-j문에 break를 넣었기때문에 그나마 괜찮지않을까...라는 생각이었거든요.

무작정 싹다 확인하는 방법이라 시간이 쓸데없이 많이 드는 것이라고 생각해도 될까요??

끝까지 읽어주셔서 감사합니다!

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

int main(void) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, temp;
	cin >> n;
	
	
	vector<int> A;
	A.push_back(0);

	for (int i = 1; i <= n; ++i) {
		cin >> temp;
		A.push_back(temp);
	}
	queue<int> NGE;
	for (int i = 1; i <n; ++i) {
		// A[i] : 현재 NGE와 비교할 대상
		// NGE[n]은 무조건 -1이므로 A[n]은 비교할 필요가 없다.
		for (int j = i + 1; j <= n; ++j) {
			if (A[i] < A[j]) {
				NGE.push(A[j]); // Ai보다 큰 수 중에서 가장 왼쪽에 있는 수
				break;
			}
			else if (j == n) {	// 그러한 수가 없는 경우
				NGE.push(-1); // 오큰수 = -1
			}
		}
	}
	NGE.push(-1); // NGE[n]은 무조건 -1

	
	for (int i = 1; i <= n; ++i) {
		cout << NGE.front() << " ";
		NGE.pop();
	}
	cout << "\n";



}

ha_ram 4년 전 1

N이100만이고

수열의 앞에 1 ~ 99만 번째 까지가 전부 다 1이고 마지막 100만번째가 10인경우에

위의 break는 의미가 없습니다.

legendmic2 4년 전 1

@ha_ram

맞네요...예외가 최소 하나라도 존재하면 break는 개뿔 그냥 이중포문인거네요ㅠㅠ 감사합니다!

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

문제

문제

출처

ICPC

시간초과 관련 질문드립니다.

legendmic2 4년 전 0

ha_ram 4년 전 1

legendmic2 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말