[BOJ/백준] 골드4 17298번 오큰수.

출처

https://www.acmicpc.net/problem/17298

문제

크기가 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)을 공백으로 구분해 출력한다.

과정

오큰수를 찾지 못한 값에 대한 인덱스를 새로운 list를 만들어서 넣고 저장하는 방법을 썼다. 1

• a[1] = 3인 경우 아직 오큰수를 찾을 수 없다.
• 그래서 스택에 1을 넣는다
• stack = [1]

2

• a[2] = 5, stack = [1]
• 스택의 가장 위에 있는 수는a[1] = 3이고 a[2] = 5이므로
• 3의 오큰수는 5가 된다.
• 3의 오큰수를 찾았으므로 stack에서 1 pop되고 stack[2]

3

• a[3] = 2, stack = [2]
• 스택의 가장 위에 있는 수는a[2] = 5이고 a[3] = 2이다.
• a[2] > a[3] 이므로 위치 3을 스택에 넣는다.
• stack = [2,3]

4

• a[4] = 7, stack = [2,3]
• 스택의 가장 위에 있는 수는a[3] = 2이고 a[4] = 7이다.
• a[3] < a[4] 이므로 2의 오큰수는 7임을 알 수 있다.
• 2의 오큰수를 찾았으므로 stack에서 3은 pop되고 stack =[2]
• a[2] < a[4] 이므로 5의 오큰수는 7임을 알 수 있다.
• 5의 오큰수를 찾았으므로 stack에서 2는 pop되고 stack = []

5

• a[4] = 7, stack = []
• 오큰수 찾기가 끝났고 stack[4]가 들어있으므로 스택에 들어있는 수는 오큰수가 -1이다.

정답 코드

시행 착오

처음에는 단순히 이중 list값들의 크기를 이중 for문을 써서 하나하나 비교해서 큰 값이 나오면 stack에 저장한 후 stack에 첫번째 값을 정답 리스트에 넣어주면 된다고 생각했고 마지막 값은 어차피 -1이 나오므로 마지막 전까지 계산 한 후 정답리스트 마지막에 -1를 추가해주는 식으로 풀게 되었는데 이렇게 푼다면 마지막말고 중간이나 처음에 제일 큰 값이 있어 버리면 -1을 넣어 줄 수 없었다.

아래는 처음 잘못짠 코드이다.

후기

list 값만 가지고 문제를 푸는 시선에서 list 값 들이 가지고 있는 인덱스 값을 가지고도 문제를 풀 수 있는 생각을 가질 수 있게 되었다.

한걸음 한걸음 나아가보자!!