[90일차][백준][자료구조, 스택][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)을 공백으로 구분해 출력한다.

 

예제 입력, 예제 출력

4 3 5 2 7	5 7 7 -1
4 9 5 4 8	-1 8 8 -1

 

코드 및 설명

import sys

n = int(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().strip().split(" ")))
stack = []
answer = []

for i in range(n):
  if len(stack) == 0:
    stack.append(i)
  else:
    for j in range(len(stack)):
      if n_arr[stack[-1]] < n_arr[i]:
        answer.append(n_arr[i])
        stack.pop()            
    
    stack.append(i)    
  
  if i == n-1:
    answer.append(-1)
    stack.pop()    
    
if len(stack) != 0:
  for val in stack:
    answer.insert(val, -1)

print(" ".join(str(val) for val in answer))

 

이 문제는 지문부터 이해하기가 어려웠다. 무슨 말을 하는지??... 오큰수는

 

3 5 2 7 이란 수가 주어졌을 때

 

첫번째 3을 기준으로 오른쪽에 있는 5 2 7 중 3보다 큰 수 중 가장 왼쪽에 있는 수가 오큰수라는 말이다.

 

즉 5 2 7 중에 3보다 큰건 5, 7이 있는 데 여기서 5가 가장 왼쪽에 있기 떄문에 오큰수는 5가 된다.

 

그 다음 5를 기준으로 오른쪽에는 2 7 이 있고 5보다 큰 수 중 가장 왼쪽에 있는 수는 7이 된다.

 

2를 기준으로 오른쪽에는 7이 있고 2보다 큰 수 중 가장 왼쪽이 7이기때문에 7이 된다.

 

마지막 7은 오른쪽에 아무것도 없기 때문에 -1이 된다.

 

5 7 7 -1이 답이 된다.

 

이걸 이제 코드로 구현하면 된다. 위에 처럼 구현했으나, 뭔가 좀 이상했다. 그래서 다시 코드를 짜보았다.

 

import sys

n = int(sys.stdin.readline())
n_arr = list(map(int, sys.stdin.readline().strip().split(" ")))
stack = []
answer = [0] * n

for i in range(n):
  while stack and n_arr[stack[-1]] < n_arr[i]:
    answer[stack.pop()] = n_arr[i]  
  stack.append(i)

if len(stack) != 0:
  for val in stack:
    answer[val] = -1

print(" ".join(str(val) for val in answer))

 

스택을 이용하여 풀었는 데, 

 

stack의 값이 비어있으면 i 즉 값의 위치값을 넣어주고, 값이 있으면 다음에 올 값과 비교를 해준다.

 

처음 스택에 [ 0 ] (n_arr[0] 즉 값은 3) 쌓이고 그 다음 위치값이 1이 오는 데 여기서 비교하는 게

 

stack의 제일 위의 값과 현재 값을 비교해준다. 스택에는 위치값이 있기 때문에 top 가져오면 

 

n_arr[stack[-1]] < n_arr[i]  =>  3 < 5  3보다 5가 크기때문에 5가 오큰수가 된다. 그러면 0번째 스택은 오큰수를 찾았고

 

answer에 0번째 자리에 n_arr[i] 즉 5값을 넣어준다. 반복을 진행한다.

 

확인해줘야하는 부분이 stack이 남아있으면 끝까지 돌았는 데도 오큰수를 못찾았거나, 마지막 번째 일 것이다. 

 

for문을 돌려 answer[val] = -1로 넣어준다. 그럼 정답이 나온다.