[백준 17298번 - Python 파이썬] 오큰수

백준 17298번 - 오큰수

Solution

조건 : 'Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다'
위와 같은 조건이 있기 때문에 스택을 이용하여 Ai보다 오른쪽에 있으면서 큰 수가 나오면
바로 그 값을 저장하고 빠져나오는 식으로 구성하면 될 것 같다고 생각하여
아래의 논리를 통해 해결하였다.

1. 오큰수가 없는 경우에는 '-1' 이기 때문에 결과값을 저장할 배열을 초기화(-1 * 수열의 크기) 해준다.

2. 배열의 index를 저장할 stack 선언

3. for문을 사용하여 첫 index를 제외한 arr의 모든 요소를 검색

4. while문을 사용하여 조건에 충족하는 수를 검색

Code

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

for i in range(1, N):
  while stack and arr[stack[-1]] < arr[i]:
    result[stack.pop()] = arr[i]
  stack.append(i)

print(*result)

Feedback
문제를 보고 어떻게 풀어야 하는지 고민하는 시간이 많이 걸렸고,
아직 스택에 대한 내공이 많이 부족하다 느꼈기에 이 점을 보완해야 할 것 같다.