[programmers] 뒤에 있는 큰 수 찾기

간만에 돌아온 코테 문제 푸는 시간!!!
이번 주 내내 프로젝트를 하느라 정신이 많이 없었다.
프로젝트 1주차 후기는 모레 코드리뷰 후에 간략하게 적고자 한다.
만든 기능, 새로 배운 내용, 개선하면 좋을 것 같은 점들에 대해서
적으면 될 것 같다.

아무튼 코테문제를 간만에 풀었다.
프로그래머스 Lv.2 뒤에 있는 큰 수

문제 분석
배열을 순서대로 탐색하면서 자신보다 뒤에 있는 index의 숫자 중에 자기보다 큰 가장 가까운 수를 차례로 담는 배열을 만드는 문제이다. 더 큰 수가 없으면 -1을 담는다.

아이디어
기본적으로 DP문제가 의심된다.
효율성 문제가 없다면 기본적으로 너무 코드가 쉽기 때문이다.

1. 배열을 탐색하면서 탐색 목표의 숫자를 now에 저장한다.
2. 다음 index부터 배열을 탐색하면서 now보다 큰 값을 만나면 즉시 break하고 answer에 해당 number를 추가한다.
3. 만약 break가 발동되지 않고, j가 마지막 인덱스에 도달했다면 자동으로 -1을 추가한다.
4. 마지막으로 i가 마지막 index인 경우에는 무조건 -1이 추가될 것이다.

일단 여기까지 코드로 구현해보았다.
첫 번재 코드

from collections import deque
def solution(numbers):
    answer = []
    for i in range(len(numbers)-1):
        now = numbers[i]  
        for j in range(i+1,len(numbers)):
            if numbers[j] > now:
                answer.append(numbers[j])
                break
            if j == len(numbers)-1:
                answer.append(-1)
    return answer + [-1]

기본적으로 논리상 문제는 없을 것이다.

이제 효율성 개선을 하면 된다.
개선점은 쉽게 생각해서, 한번 찾은 "다음 큰 수"가 언제 바뀌는지
생각해보면 될 것이다.
[9, 1, 5, 3, 6, 2] 이런 배열에서 result 값은
[-1, 5, 6, 6, -1, -1] 이다.
여기서 5 다음 큰 수는 6이므로 6이 추가되었는데,
다시 검색을 해야 하는 순간은 index 값이 그 6을 만났을 때이다.
그러니까 마지막으로 찾은 큰 수와 같은 값을 만나기 전까지는
이후 배열을 탐색할 필요도 없다는 뜻이다!
이 내용을 코드로 추가하였다.

---

그런데도 잘 안된다 ㅋㅋ

다른 방법이 필요한 것 같다.

1. j == len(numbers)-1: 부분 대신, answer 리스트를 기본적으로 -1로 채워서 사용하는 아이디어
2. 스택 자료구조를 사용하는 방법

stack 자료구조를 사용할 경우

def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []
    for i in range(len(numbers)):
        while stack and numbers[stack[-1]] < numbers[i]:
            idx = stack.pop()
            answer[idx] = numbers[i]
        stack.append(i)
    return answer

1. stack이 비어있지 않고, 다음 큰 수를 발견할때까지 index를 계속 추가한다. (추가한 index들에는 다음 큰 수를 다시 넣어야 한다.)
2. 만약 다음 큰 수를 만족하는 조건을 찾았다면, stack에서 해당 index를 빼내서, 그 index에 해당하는 answer 값을 그 값으로 바꿔준다. 스택이 아직 남아있다면 계속해서 그 작업을 해준다.
3. 조건이 만족되지 않아, 수정이 되지 않은 값은 처음에 -1로 초기화 해두었기 때문에 그대로 -1이 출력된다.

이 문제는 다른 풀이가 많을 것으로 생각된다
다른 풀이 1

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

backmax : 현재 위치의 뒤에서 가장 큰 뒷 수가 없는 수
(즉 -1이 return되는 가장 큰 수)
이런 방법을 이용해서 푼 예시가 있었다. 아주 신묘한 풀이이다.

다른 풀이 2

def solution(numbers):
    answer = []
    st = [9999999]
    for number in numbers[::-1]:
        while number >= st[-1]:
            st.pop()
        if st[-1] == 9999999:
            answer.append(-1)
        else:
            answer.append(st[-1])
        st.append(number)

    answer.reverse()

    return answer

비슷한 풀이방법인것 같다.
핵심 아이디어는 뒤에서부터 찾는 게 훨씬 효율적이라는 것이다.