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

문제 설명

출처 : 프로그래머스 코딩테스트 연습 문제 - 뒤에 있는 큰 수 찾기

해결 코드

스택을 사용해서 간단하게 해결하였다. 알고리즘을 어느정도 풀다보니, 문제 유형이 눈에 들어오기 시작했다.

def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []
    for i, number in enumerate(numbers):
        while stack and stack[-1][1] < number:
            j, _ = stack.pop()
            answer[j] = number
        stack.append((i, number))
    return answer

 

 

코드 해설

입출력 예제 2번을 바탕으로 풀이 진행 하였습니다.

메인 로직 1

# numbers = [9, 1, 5, 3, 6, 2]
def solution(numbers):
    answer = [-1] * len(numbers)
    stack = []

파라미터로 들어오는 nubers의 길이 만큼 -1로 구성 된 배열과, stack 이라는 빈 배열을 만든다.

 

 

 

메인 로직 2

for i, number in enumerate(numbers):
        while stack and stack[-1][1] < number:
            j, _ = stack.pop()
            answer[j] = number
        stack.append((i, number))

1. for i, number in enumerate(numbers) : for문 사용하면서 index와 value값을 한번에 stack에 튜플 형식으로 저장한다.

2. while stack and stack[-1][1] < number : stack이 비어있지 않거나, stack의 value값이 다음으로 들어오는 nuber보다 작다면,

3. j, _ = stack.pop() : stack 배열에 가장 마지막 값의 인덱스값을 j에 저장한다.

4. answer[j] = number : j의 값 즉 (number array에서 원래 자신의 인덱스 값)을 아까 -1들로 초기해 둔 값들에 저장한다.

5. stack.append((i, number)) : while문을 만족하지 않을때는 그냥 스택에 계속해서 값을 쌓는다.

위 과정 반복하면 문제 해결 가능