글 읽기 - 틀렸다고 나오는데 반례를 모르겠어요ㅠㅠ

mareng825 4년 전 0

틀렸다고 나오는데 아무리 봐도 왜 틀렸는지 모르겠습니다.

NGE를 출력해야 하는 원소를 key로 두고, 그 이전 NGE 값 이후부터 탐색하도록 했습니다.

beforeIndex는 이전 NGE 값, ngeIndex는 이제 구해야 하는 NGE값입니다.

예를 들어,

2 1 1 1 7 8

이렇게 입력했다면

2의 NGE값을 7로 출력하고, 1의 NGE값을 계산할 때는 7부터 찾는 것입니다.

아무리 봐도 반례가 나오지 않아 글 올립니다.

#include <iostream>
using namespace std;

int n;
int arr[1000000] = { 0, };
int ngeIndex, beforeIndex = 1;

int main() {
	
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	for (int i = 0; i < n; i++) {
		int key = arr[i];
		
		for (ngeIndex = beforeIndex; ngeIndex < n ; ngeIndex++) {
			if (key < arr[ngeIndex]) {
				cout << arr[ngeIndex];
				if (i < n-1) cout << " ";
				beforeIndex = ngeIndex;
				break;
			}
		}
		if (ngeIndex >= n) {
			cout << "-1";
			if (i < n-1) cout << " ";
			beforeIndex++;
		}
	}

}

gmd1356 4년 전 0

지금 작성하신 코드는

2 1 2 1 7 8 일경우

NGE(2)일때 2가 나와야 되는데 7이 나오게 짜셧네요

mareng825 4년 전 0

아 그렇군요! 이제 알겠네요 감사합니다ㅠㅠ

그럼 시간초과가 안 나게 하려면 스택으로 푸는 방법밖에 없을까요?

gmd1356 4년 전 0

그럴것 같네요 아니면 배열을 그냥 스택처럼 이용하셔도... 이게 더 귀찮겟지만요

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

문제

문제

출처

ICPC

틀렸다고 나오는데 반례를 모르겠어요ㅠㅠ

mareng825 4년 전 0

gmd1356 4년 전 0

mareng825 4년 전 0

gmd1356 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말