[Baekjoon] 17298: 오큰수

문제

각 원소 A_i에 대해 오른쪽에 있으면서 A_i보다 큰 수 중에서 가장 왼쪽에 있는 수를 구하는 문제이다. (없을 경우 -1)

예를들어 3 5 2 7 이라는 수열이 있으면,

3의 오큰수는 5, 5의 오큰수는 7, 2의 오큰수는 7, 7의 오큰수는 없으므로

5 7 7 -1 이라는 결과가 나오게 된다.

 

풀이

내 풀이

import sys

input = sys.stdin.readline

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

result = [0] * len(arr)
stack = [0]
for i in range(1, len(arr)):
    while stack and arr[i] > arr[stack[-1]]:
        result[stack.pop()] = arr[i]
    stack.append(i)

for i in stack:
    result[i] = -1

print(*result)

이 문제를 전부 탐색하려한다면 O(n^2)만큼의 시간복잡도가 나오기 때문에 시간초과가 날 것이다. 때문에 더 효율적으로 수행할 수 있는 코드를 구상해야한다.

 

여기선 효율적인 풀이를 위해 스택을 활용할 것이다.

스택을 통해 어떻게 이 문제를 해결할 수 있을까?

 

먼저 요소들의 관계를 한 번 살펴보자

 

각 요소를 x(i), x(i+1), x(i+2)라 해보자

x(i)를 기준으로 봤을 때 경우는 두 가지가 나올 수 있다.

1. x(i) < x(i+1)
2. x(i) >= x(i+1)

여기서 1번의 경우엔 간단하다. 바로 x(i+1)이 오큰수이다.

유심히 살펴봐야될 것은 2번의 경우이다. x(i+1)이 x(i)보다 작거나 같다면 그 다음 어떻게 비교해야될지 생각해봐야된다.

여기서 단지 x(i)와 x(i+2)를 비교하려하면 위에서 말한 완전탐색과 다를 것이 없다.

우리는 스택으로 구현하기로 했기 때문에 x(i+1)을 스택에 넣고 x(i+1)과 x(i+2)를 비교하는 방법을 생각해볼 수 있을 것이다.

 

x(i+1)과 x(i+2)를 비교할 때도 위와 같이 두 가지 경우가 나온다.

1. x(i+1) < x(i+2)
2. x(i+1) >= x(i+2)

1번의 경우엔 당연히 x(i+2)가 x(i+1)의 오큰수가 된다. 여기서 위와 다른 점은 x(i)와도 비교를 해봐야된다는 것이다. 때문에 스택에서 하나씩 빼가며 오큰수가 아닐때 까지 비교를 하면 될 것이다.

2번의 경우엔 위와 같은 경우로 x(i+2)와 x(i+3)을 비교하거나, x(i+2)가 마지막 요소라면 -1을 넣으면 된다.

말을 좀 어렵게 한 느낌이 있는데, 간단히 생각하여 바로 다음 요소와 비교해서 오큰수가 아니면 계속 스택에 넣다가, 나오면 스택 요소를 빼가면서 비교해보는 것이다.
위의 요소들을 예를 들어 설명하면, 각 요소들의 바로 오른쪽 요소와 비교하여 오큰수가 아니라면 요소들의 관계는 x(i) >= x(i+1) >= x(i+2) 이렇게 될 것이다. 때문에 더 큰 요소가 나올 때 까지는 오큰수가 없다해도 무방하다.

 

이렇게 비교하면 중복된 검사를 줄여 실행시간을 줄일 수 있을 것이다.

 

자세한 구현은 코드를 참고하자

 

회고

처음 문제를 풀 때 방법이 떠오르지 않아 많이 막혔던 문제였다.

어떻게 하면 방법을 잘 떠올릴 역량을 기를 수 있을까 계속 고민이된다.

물론 문제를 많이 푸는 방법이 전부일 수 있겠지만, 좀 더 역량을 기를 방법을 찾아보며 공부해봐야겠다.