19th KOALA 8주차

코알라 8주차~!!( •̀ ω •́ )✧

 

 

백준 17298번 : 오큰수 

 

수열 A가 있을 때, 각 원소 Ai에 대해서 Ai의 오른쪽에 있으면서 Ai보다 큰 수 중 가장 왼쪽에 있는 수를 구하는 문제이다.
만약 그런 수가 존재하지 않으면 -1을 출력해야 한다!!

 

먼저 내 전체 코드는 이러하다!!  ‎(  ˘ω˘ )و ̑̑

import sys
input = sys.stdin.readline

n = int(input())
A = list(map(int, input().split()))

ans = [-1] * n        # 기본값은 -1(오큰수가 없을 수도 있으므로)
st = []               # 인덱스를 저장할 스택

for i in range(n):
    # 스택이 비어있지 않고, 현재 값이 스택 top 인덱스의 값보다 크면
    while st and A[st[-1]] < A[i]:
        ans[st.pop()] = A[i]   # 그 인덱스의 오큰수를 현재 값으로 갱신
    st.append(i)               # 현재 인덱스를 스택에 push

print(*ans)

 

 

 

코드를 하나하나 설명해보자면...!! ( ⸝•ᴗ•⸝)

ans = [-1] * n
st = []

기본적으로 모든 원소의 오큰수를 -1로 초기화한다. (없으면 그대로 -1을 반환한다!)

st는 아직 오큰수를 찾지 못한 인덱스를 저장할 스택이다. 

 

 

for i in range(n):

    while st and A[st[-1]] < A[i]:
        ans[st.pop()] = A[i]  
    st.append(i)

 

먼저 배열을 왼쪽에서 오른쪽으로 탐색하면서, 현재 값(A[i])을 기준으로 스택에 쌓인 값들과 비교한다.

스택에는 "아직 오큰수를 찾지 못한 인덱스들"이 저장되어 있다. 만약 현재 값이 스택 top 인덱스의 값보다 크다면, 그 인덱스의 오큰수는 현재 값임이 확정된다. 따라서 ans[st.pop()] = A[i]로 오큰수를 갱신한다. 현재 값도 앞으로 나올 값들에 대해 오큰수가 될 수 있으므로 스택에 넣는다. (⌒▽⌒)☆