문제
크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.
- 입력
첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.
- 출력
총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.
- 예제 입력 1
4 3 5 2 7
- 예제 출력 1
5 7 7 -1
- 예제 입력 2
4 9 5 4 8
- 예제 출력 2
-1 8 8 -1
- 첫번째 시도
n = int(input()) a = list(map(int, input().split())) for _ in range(n): answer = [] ai = a[0] del a[0] for i in a: if ai < i: answer.append(i) if len(answer) != 0: print(answer[0]) else: print(-1)
- 두번째 시도
import sys input = sys.stdin.readline n = int(input()) a = list(map(int, input().split())) for _ in range(n): answer = [] ai = a[0] del a[0] for i in a: if ai < i: answer.append(i) if len(answer) != 0: print(answer[0]) else: print(-1)
- 내가 구현한 코드는 정상적으로 출력이 잘 나오지만 시간초과를 해결하지 못했다
- 정답
import sys input = sys.stdin.readline n = int(input()) seq = list(map(int,input().split())) stack = [] for i in range(n): while(stack): if seq[i] > seq[stack[-1]]: seq[stack.pop()] = seq[i] else: stack.append(i) break if not stack: stack.append(i) for i in stack: seq[i] = -1 print(*seq)