156. 17298(오큰수) - 파이썬

import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
result = ["-1"] * N
stack = []

for i in range(N):
    try:
        while A[stack[-1]] < A[i]:
            result[stack.pop()] = str(A[i])
    except:
        pass

    stack.append(i)

print(" ".join(result))

문제요약

입력값에 오큰수를 구해라.

오큰수란?

A=A1 ~ AN이 있을 때 Ai번째의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중 가장 왼쪽에 있는 수이다.

다시 말해 지금 수 보다 크고, 인덱스 크기가 가장 작은 수 

설명

입력 예시로

백준에 있는 다음과 같은 예시를 들어보자.

3과 5를 비교했을 때 5가 더 크다. 따라서 답은 5가 된다.

답이 7이 될 수 없는 이유는 오큰수는 N보다 오른쪽에 있으면서 가장 왼쪽에 있는 수이다.

다음 5는 먼저 2보다 크다 그래서 2가 될 수 없고 7은 5보다 크기 때문에 가능하다.

2도 7이 더 크기 때문에 7이 나온다.

7의 오른쪽에는 수가 없을 뿐만 아니라 7보다 더 큰 수도 없기 때문에 -1이 나온다.

따라서 답은 5 7 7 -1이다.

전체적인 맥락은 이렇다.

 

result = ["-1"] * N

먼저 모두 오큰수가 없는 경우인 -1로 초기화 했다.

문자열로 작성한 이유는 나중에 join을 쓰기 위해서이다.

문자열이 눈에 거슬린다면 나중에 join 대신 반복문을 사용하면 된다.

    try:
        while A[stack[-1]] < A[i]:
            result[stack.pop()] = str(A[i])

stack에 값이 없다면 에러를 불러 일으킬 것이다.

그것을 이용하여 try / except문을 사용했다.

 

A[stack[-1]]이 기준이다.

기준을 중심으로 오른쪽의 크기 A[i]가 크다면 while문을 계속 진행한다.

 

result에 stack 값을 꺼내 인덱스로 정하고, 크기가 더 큰 오른쪽 값을 집어 넣는다.

여기도 역시 문자열로 변경해준 이유는 나중에 join문은 사용하기 위해서이다.

    except:
        pass

    stack.append(i)

try except문이 종료되면 stack에 i값을 집어넣는다.

아직 i번째의 오큰수를 구하지 않았기 때문이다.