[BOJ 17298]오큰수(Python)

문제링크

오큰수

풀이 전 계획 및 생각

N개의 데이터에대해서 순서대로 하나씩 오큰수를 찾는 방식을 사용했다.
정답을 저장할 ans_array를 -1로 초기화해서 오큰수가 없는 경우에는 별도의 처리없이 -1을 출력할 수 있게했다.

stack에는 수열의 index를 저장한다. stack을 사용한 이유는 오른쪽에 있는 숫자들만 봐주고, 현재 보려는 값 이전의 데이터는 무시하면 되기때문에 사용했다.

stack에는 다음 3가지 경우로 나누어서 원소를 추가한다.
1) 스택이 비어있으면 stack에 현재 원소의 index를 push해준다.
2) i번째 원소를 보고있을 때, 스택의 top원소가 현재 보고있는 i번째 원소보다 큰 경우에는 오큰수가 될 수 없기 때문에, i번째 원소를 stack에 push한다.
3) 경우 2)에 해당하지않는 경우에는 현재 보고있는 i번째 원소는 현재 stack의 top에 있는 index에 해당하는 원소의 오큰수가된다.(즉, num[stack[top]]보다 오른쪽에 있으면서 num[i]보다 큰 수라는 뜻이다.) 이 연산을 stack이 비거나 stack의 top에 있는 index에 해당하는 원소보다 현재 보고있는 i번째 원소가 작아질 때까지 반복해준다.

풀이

import sys

n = int(sys.stdin.readline())
num = list(map(int,sys.stdin.readline().split()))
stack = []
ans_array = [-1]*n
for i in range(n):
    if stack:
        if num[stack[-1]] >= num[i]:
            stack.append(i)
        else:
            while stack and num[stack[-1]] < num[i]:
                temp = stack.pop()
                ans_array[temp] = num[i]
            stack.append(i)
    else: stack.append(i)

for data in ans_array:
    print(data,end= ' ')

풀이하면서 막혔던 점과 고민했던 점

딱히 막히는 점은 없었다. 처음에는 stack에 현재 index와 현재 num[index]를 같이 저장했었는데, 이게 정말 비효율적인 방법이였다. 그래서 정답을 받은 후에 위의 풀이코드와 같이 코드를 개선했다.

풀이 후 알게된 개념과 소감

생각보다 스택을 활용할 수 있는 부분이 많다는 것을 알았다. LIFO를 적용할 수 있으면 제일 먼저 떠올려야겠다.