[프로그래머스] Lv2. 뒤에 있는 큰 수 찾기

📝 문제

자신보다 크면서 가장 가까이에 있는 수를 찾아라

풀이

💡 아이디어

일단 당연히 브루트포스로 풀어봤고 시간초과가 발생했다. 배열의 길이 범위가 백만이기 때문에 O(n^2) 방식으론 사실상 불가능

다음은 힙 자료구조를 활용해봤다. O(n^2)이 안 된다면 O(nlogn)은 가능할 수도 있을 거 같았다. 하지만 가장 가까이에 있으면서 현재 숫자보다 큰 숫자를 찾는 방식의 정렬이 안 됐다. 가장 가까운 숫자를 찾아버리거나, 가장 큰 숫자를 찾아버리거나 둘 중 하나만 가능해서 이 방법도 포기

🏢 스택을 활용한 풀이

가장 가까이에 있는 자신보다 큰 수 라는 말이 힌트가 될 수 있을 거 같다. 가장 가까이에 있다 = 현재 자신의 값과 비교했을 때 가장 가까운, 가장 최신의 값으로 해석할 수 있다. 가장 나중에 들어온 값이 가장 먼저 비교되는 스택의 구조를 활용하면 된다.

배열 arr = [1, 3, 5, 2, 4]가 있을 때 뒤에서부터 비교하면서 스택에 쌓는다고 가정하자

[4]
[4, 2]
[4, 2, 5]

이렇게 될 때 arr[1] = 3의 값과 가장 먼저 비교되는 값은 5이다. 가장 나중에 들어왔으면서 3과의 거리가 가장 가까운 값이 된다. 즉, 스택은 현재 위치의 값 직전의 값이 가장 top에 저장되어 있다. 그 값부터 차례대로 비교하면 훨씬 수월하다.

단, 이때 O(n^2)이 되지 않기 위해서는 아래와 같이 조건을 지켜야 한다

✅ 스택의 top 값과 비교해서 현재의 값보다 작은 값들은 pop

어차피 이 값들은 현재의 값보다 작기 때문에, 현재의 값보다 앞에 있는 값들보다 큰 값이 될 수 없다. 현재의 상황에서 현재 값보다 앞에 있는 값들이 갖게 될 뒤의 큰 수는 현재의 값이다. 더 작은 값들은 스택에 쌓여 있을 필요가 없으므로 제거한다

✅ 스택의 top 값과 비교해서 더 큰 값은 answer에 추가

이 값은 현재의 값보다 크면서 뒤에서 가까운 위치에 있는 숫자이다. 더 뒤에 더 큰 수가 있을 수도 있지만 그 값들은 이 값보다 멀리 있는 값이기 때문에 비교할 필요가 없다. 이 값은 현재의 값보다 앞에 있는 값들 중에 현재 값보다 더 큰 값이 들어왔을 때 비교대상이 될 가치가 있으므로 스택에 내버려 둔다

✅ 비교된 모든 값들은 스택에 추가된다

현재 값보다 더 작은 값들은 모두 제거했으므로 이제 현재의 값은 스택에 추가한다. 현재 값보다 앞에 있는 값들 중에 현재 값보다 작은 값은 이 현재 값을 답으로 갖게 될 것이다. 만약 앞서 값들이 현재 값보다 더 크다면 이 값은 제거 될 것이다. 하지만 어쨌든 이 문제는 가장 큰 값을 찾는 것은 아니기 때문에 위치를 비교해나가기 위해서 모든 값들은 일단 스택에 저장해둔다.

def solution(numbers):
    L = len(numbers)
    answer = [-1]*L
    
    stack = [numbers[-1]]
    for i in range(L-2, -1, -1):
        x = numbers[i]
        
        while stack:
            if x < stack[-1]:
                answer[i] = stack[-1]
                break
            stack.pop()
        stack.append(x)
        
    return answer

🕹️ DP를 활용한 풀이

이 풀이는 이 코드를 참조 했습니다

배열의 뒤에서부터 비교하면서 값을 저장해나가는 dp

1️⃣ 뒤에 나보다 큰 값이 있으면 저장하고 종료

2️⃣ 뒤의 값이 나보다 작거나 같으면서 answer = -1 일 때

뒤에 더 큰 값이 없다는 뜻이므로 현재 값도 -1

3️⃣ 작거나 같으면서 answer가 0은 아닐 때

값을 비교하고 현재 값보다 크면 저장,
하지만 그 값도 현재 값보다 작다면 한 칸 더 뒤로 넘어가서 1~3 과정 반복

def solution(numbers):
    L = len(numbers)
    answer = [-1]*L
    
    for i in range(L-2, -1, -1):
        j = i + 1
        while j < L:
            if numbers[i] < numbers[j]:
                answer[i] = numbers[j]
                break
            
            if answer[j] == -1:
                answer[i] = -1
                break
            
            if numbers[i] < answer[j]:
                answer[i] = answer[j]
                break
                
            j += 1
            
    return answer