[백준] 17298. 오큰수 풀이 / Python, JavaScript

17298번: 오큰수

 

작성 코드 (.py)

import sys
input = sys.stdin.readline

n = int(input())
table = list(map(int, input().split()))
s = []
result = [-1 for _ in range(n)]
for i in range(len(table)):
    while s and s[-1][0] < table[i]:
        v, idx = s.pop()
        result[idx] = table[i]
    else:
        s.append((table[i], i))
print(*result)

작성 코드 (.js)

function solution(n, numbers) {
  const result = Array(n).fill(-1);
  const s = [];
  numbers.forEach((number, i) => {
    while (s.length && s[s.length - 1][0] < number) {
      const [v, idx] = s.pop();
      result[idx] = number;
    }
    s.push([number, i]);
  });
  return result;
}

 

구현 로직 (스택)

스택을 활용합니다. 현재 스택에 값이 들어있고 현재 확인한 숫자(A)가 스택의 상단 값(B)보다 큰 경우 이 A숫자가 B수의 오큰수가 됩니다. 예제 수열 3, 5, 2, 7에 대한 예시 과정입니다.

 

인덱스	현재 확인중인 수	스택	결과 배열
초기	-	[]	[-1, -1, -1, -1]
0	3	[[3, 0]]	[-1, -1, -1, -1]
1	5	[[5, 1]]	[5, -1, -1, -1]
2	2	[[5, 1], [2, 2]]	[5, -1, -1, -1]
3	7	[[7, 3]]	[5, 7, 7, -1]

1. 현재 확인중인 수가 3일 때, 스택에 값이 없으므로 값과 인덱스를 스택에 넣어줍니다.

2. 현재 확인중인 수가 5일 때, 스택에 값이 들어있으므로 스택의 최상단 값이 5보다 클때까지 스택에서 값을 꺼냅니다. 꺼내진 값의 인덱스에 오큰수인 5를 넣어줍니다. 과정이 끝나면 5의 오큰수도 확인해야하므로 5와 5의 인덱스를 스택에 넣어줍니다.

3. 현재 확인중인 수가 2일 때, 스택에 값이 들어있지만 최상단 값인 5가 더 크므로 2를 스택에 넣어줍니다.

4. 현재 확인중인 수가 7일 때, 스택에 값이 들어있으므로 스택의 최상단 값이 7보다 클때까지 스택에서 값을 꺼냅니다. 꺼내진 값의 인덱스에 오큰수인 7을 넣어줍니다. 과정이 끝나면 7의 오큰수도 확인해야하므로 7과 7의 인덱스를 스택에 넣어줍니다. 더이상 수열이 없으므로 그대로 종료합니다.

5. 오큰수가 등록되지 않은 수는 초기값인 -1이 그대로 들어있으므로 오큰수가 없는 경우를 의미합니다.