새싹프로그래머의 이야기

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

문제: 오른쪽에서 큰 수중 제일 왼쪽에 있는 수를 구하는 문제

풀이 방법: 스택

풀이 코드:

import sys
from collections import deque

n = int(input())
array = list(map(int, sys.stdin.readline().rstrip().split()))
stack = deque()
ans = [-1]*n

for i in range(n-1,-1,-1):
    while stack:
        if stack[-1] > array[i]:
            ans[i] = stack[-1]
            stack.append(array[i])
            break
        else:
            stack.pop()

    stack.append(array[i])

print(' '.join(map(str,ans)))

풀이 설명:

풀이에서 핵심으로 잡은 점은 두가지 입니다.

1. 스택의 활용

2. 오른쪽에서 큰 수 중 제일 가까운 수를 구하는 문제이므로, 오른쪽부터 탐색

핵심이 되는 코드를 보면 다음과 같습니다.

for i in range(n-1,-1,-1):
    while stack:
        if stack[-1] > array[i]:
            ans[i] = stack[-1]
            stack.append(array[i])
            break
        else:
            stack.pop()

    stack.append(array[i])

오른쪽부터 탐색을 하면서, 스택에 큰 값을 담습니다.

이때, 스택에 담긴  A라는 값보다 더 큰 B라는 값을 만나게 되면 B 왼쪽의 수들에게는 더 이상 A가 의미가 없어지므로 pop 하도록 하였습니다.

if stack[-1] > array[i]:
    ans[i] = stack[-1]
    stack.append(array[i])
    break

스택의 마지막 값이 더 크다면, 현재 배열의 값의 오큰수는 스택에 담긴 값 입니다.  

따라서, 정답 값을 저장하는 ans에 저장해줍니다.

또한, 현재 배열의 값이 오큰수 일 수 있으므로 스택에 담아줍니다.

else:
    stack.pop()

만약, 현재 배열의 값이 스택의 마지막 값보다 크다면 pop을 해줍니다.

이유는 배열의 값이 더 크기 때문에 앞으로 스택의 마지막 값이 오큰수가 될 가능성이 없기 때문입니다.

마지막으로, ans를 -1로 초기화 해주었기 때문에, 스택에 담겨있는 값들보다 큰 값의 경우 현재 값의 위치의 ans에는 -1이 담겨있게 됩니다.