[PS] 백준#17298 오큰수 / 파이썬

suram·2021년 7월 24일

ProblemSolving

목록 보기

6/8

알고리즘 문제 풀이

문제 : 오큰수
해결 : unsolved
분류 : 스택

내 풀이 방법

일단 스택인 것은 알았다.
배열을 for문으로 순회하면서 스택에는 해당노드보다 더 큰 값들만 있게한다.
top이 현재 노드 보다 크거나 스택이 비었으면 -1
현재 노드보다더 작은 값이 있다면 smaller 스택에 push
스택을 끝까지 순회하고 스택이 비었으면 smaller의 값들을 다시 넣어줌
소스코드

import copy
N = int(input())
arr = list(map(int, input().split()))
stack = copy.deepcopy(arr[::-1])
smaller = []
nums = []
for i in range(N-1):
    while stack:
        top = stack[-1]
        if top < arr[i] :
            smaller.append(top)
            stack.pop()
        elif top == arr[i]:
            stack.pop()
            continue
        elif top > arr[i]:
            break

    if stack != []:
        nums.append(str(stack[-1]))
        while smaller:
            smaller.pop()
    else:
        nums.append(str(-1))
        while smaller:
            stack.append(smaller.pop())

print(' '.join(nums+['-1']))

정답 풀이

스택에는 인덱스를 저장한다

현재 노드와 바로 오른쪽 노드만 비교한다. (스택을 순회할 필요x)

비교하여 오큰수를 찾았다면 해당 인덱스를 스택에서 pop

오큰수를 찾지 못했다면 pop하지 않고 계속 인덱스를 push 한다.

만약 스택에 [5,3,4] 가 있고 현재 노드가 6일 때 스택에 있는 모든 수의 오큰수는 6이 된다. 따라서 pop을 해주면서 오큰수를 갱신해준다. 그리고 6을 push한다.

다음(6의 오른쪽) 노드는 스택의 top (=6)을 peek해서 비교하면서 반복한다.

정답 소스코드


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

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

print(*nums)