[백준] 17298 - 오큰수 (재귀 풀이)

https://www.acmicpc.net/problem/17298

17298번: 오큰수

문제 설명을 간단하게 하면, 내 오른쪽에 있는 숫자들 중, 나보다 큰 첫번째 숫자를 찾는 문제이다.

 

5 2 3 8 이면,

5 입장에서 오른쪽에서 가장 처음만나는 자기보다 큰 숫자는 8,

2 입장에서도 8

3 입장에서도 8이다.

 

https://www.acmicpc.net/problem/14659

14659번: 한조서열정리하고옴ㅋㅋ

이 문제를 풀고 오면 이해하기가 편하다.

난이도가 쉬운 아래 문제를 풀고, 이 문제를 푼다면 좀 더 편하게 느껴질 것이다.

 

가장 먼저 떠올릴 수 있는 방법은 각각의 숫자마다 자기 오른쪽을 다 체크하는 방법일 것이다.

하지만 이렇게 풀면 시간복잡도가 O(n^2) 이므로, 최대 100개의 입력을 받을 수 있는 위 문제에서는

시간초과를 피할 수가 없다.

 

따라서 나는 선형적으로 한번 체크한 숫자를 한번 더 체크하지 않는 방식으로 푸는 방법을 고민했다.

 

맨 처음에 떠올린 방법은 다음과 같았다.

왼쪽에서 숫자를 하나 체크하고, 해당 숫자보다 작은 숫자를 만나는 동안 카운트를 센다.

그 후 자기보다 큰 숫자를 만나면 그동안 카운트를 센 숫자들은 모두 오큰수를 해당 큰 수로 설정한다.

 

5 4 2 1 6

다음과 같은 숫자가 있다고 한다면, 맨 처음 5를 저장해두고,

5보다 큰 숫자가 나올 때까지 지나간 숫자들은 모두 카운트를 세고 넘긴다.

5보다 큰 숫자인 6을 만나는 순간, 지금까지 센 카운트 4와, 이 4개 숫자에 대한 오큰수 6을 따로 저장한다.

이렇게 카운트 리스트, 오큰수 리스트를 모아놓고

나중에 출력할 땐, 오큰수 리스트에 있는 수를, 같은 인덱스의 카운트 리스트 숫자만큼 반복해서 출력한다.

 

n = int(input())
nums = list(map(int, input().split()))
sort_nums = sorted(nums)
count = []
oknum = []
now_count = 0
now_num = -1

for i in range(n):
    if now_num == -1:
        now_num = nums[i]
        now_count += 1
    elif now_num >= nums[i]:
        now_count += 1

    else:
        count.append(now_count)
        oknum.append(nums[i])
        now_count = 1
        now_num = nums[i]

if now_count > 0:
    count.append(now_count)
    oknum.append(-1)

for i in range(len(count)):
    for j in range(count[i]):
        print(oknum[i], end=' ')

하지만 이 코드의 반례는 너무나도 쉽게 나온다.

5 1 2 4 6

이렇게 수열이 있다고 해보자.

 

그렇다면 위 알고리즘은 아까와 마찬가지로 작동하면서 출력을

6 6 6 6 -1

이렇게 할 것이다.

하지만 정답은

6 2 4 6 -1 이다.

 

5보다 작은 숫자들이 5와 같은 오큰수를 가진다는 보장이 되지 않는 것이 이 알고리즘의 문제다.

 

그래서 이 문제를 해결하기 위해 어떻게 할지 고민하다가 다음과 같은 알고리즘을 떠올렸다.

우선 이 알고리즘을 떠올리는데는 아까 소개했던 한조 문제가 도움이 되었다.

 

이 문제를 그림으로 도식화하면 다음과 같다.

화살표로 가리키는 숫자가 오큰수이다.

나는 이 문제를 거꾸로 생각해보았다.

 

거꾸로 7에서부터 돌면서, 자기 자신을 오큰수로 가지게 되는 막대를 찾는 것이다.

이때, 자기보다 작은 수를 만나면, 해당 수 입장에서 다시 자기 자신을 오큰수로 가지는 수를 찾는다.

그러다가 자기 보다 큰 수를 만나면, 더이상 자기는 오큰수가 될 수 없기 때문에, 멈추고,

자기 이전 오큰수를 찾는 수에게 이어서 오큰수를 찾도록 한다.

 

말로 풀어 설명하면 복잡해보이지만 간단하게 위 예시를 사용하여 정리하면 다음과 같다.

 

1. 7 입장에서 거꾸로 탐색을 시작한다.

2. 자기(7)보다 작은 수(2)를 만나면, 해당 수의 오큰수를 자기(7)로 설정한다.

 

3. 재귀적으로 2입장에서 거꾸로 탐색을 시작한다.

4. 자기(2)보다 작은 수를 만나면, 해당수의 오큰수를 자기(2)로 설정한다.

5. 만약 만나지 못했다면 자신의 인덱스를 return 하고 함수를 종료한다.

 

6. 7 입장에서, return 받은 인덱스부터 다시 탐색을 진행한다.

7. 자기(7)보다 작은 수(4)를 만나면 해당 수의 오큰수를 자기(7)로 설정한다.

 

8. 재귀적으로 4 입장에서 거꾸로 탐색을 시작한다.

... 이하 반복

 

이렇게 문제를 풀면, 한번 방문했던 수를 두번다시 방문하지 않는다.

 

즉, 나보다 작은 수를 만나면, 그 수에게 자기보다 작은 수의 처리를 맡기고

그 수가 처리한 결과를 돌려주면, 나는 그 수가 처리한 결과 이후부터 처리해나가면 되는 것이다.

 

이 알고리즘을 코드로 구현하면 다음과 같이 구현된다.

 

import sys
sys.setrecursionlimit(10**8)
def f(index):
    num = nums[index]
    while True:
        if index == 0:
            return -1
        index -= 1
        if nums[index] < num:
            oken[index] = num
            index = f(index) + 1
        else:
            return index

n = int(input())
nums = list(map(int, input().split()))
oken = [-1 for _ in range(n)]
index = n-1
while True:
    index = f(index) + 1
    if index == 0:
        break
    index -= 1
print(*oken)

 

위 코드로 AC를 받을 수 있었다.