[ 프로그래머스 ][ lv2 ] 뒤에 큰 수 찾기 ( 파이썬 Python ) (Stack을 사용하지 않은 풀이)

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

코드

---

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

 

풀이

---

찾아보니 다들 Stack을 이용해서 해결했던데 나는 DP를 사용해봤다.

DP테이블을 따로 만들지는 않았지만 backMax라는 수 하나를 사용함으로써 시간을 많이 단축시킬 수 있었다.

 

뒷 큰수가 존재하지 않는 경우에는 -1을 담아야 하는데 이런 경우가 좀 많다고 생각이 들어서 기본값을 -1로 넣어주고 뒷 큰수가 존재할 때만 값을 바꿔주었다.

 

먼저 맨 뒤는 당연히 뒷 큰수가 없으므로 backMax로 초기화하고 맨 뒤에서 두번째 수부터 탐색한다.

backMax란 현재 위치의 뒤에서 가장 큰 뒷 큰수가 없는 수이다. 즉, -1을 갖는 가장 큰 수이다.

 

만약 내 값이 backMax보다 크거나 같다면 당연히 backMax의 위치 뒤로도 나보다 큰 수는 없다. 따라서 backMax를 갱신해주고 넘어간다.

 

backMax보다 작다면 내 뒤에는 backMax보다 작지만 나보다는 큰 수가 존재할 수 있다.

순차적으로 탐색하면서 나보다 큰 수가 있다면 그 값을 저장해준다.

 

만약에 나보다 작거나 같은 수인데 그 값의 뒷 큰수가 나보다 크다면 그 뒷 큰수를 내 위치에도 저장한다.

이 부분이 조금 어려울 수 있어서 예시를 좀 들어볼까 한다.

만약에 [9, 1, 5, 3, 6, 2] 과 같은 예시가 있을 때, 답은 [-1, 5, 6, 6, -1, -1]이 된다.

중간에 5,3을 보게되면 3은 5보다 작거나 같은 수인데 3의 뒷 큰수는 6으로 5보다 크다. 따라서 5는 3의 뒤로 가더라도 6보다 빠른 뒷 큰수를 만날 수 없다. 따라서 5의 뒷 큰수는 6이 된다.

 

이렇게 DP와 조건들을 사용해서 시간초과를 통과시킬 수 있었다.

backMax라는 변수를 사용하는 아이디어는 나밖에 하지 않은 것 같아서 아주 기분이 좋다.