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

 

첫 번째 풀이

def solution(numbers):
    answer = [-1] * len(numbers)
    
    for i in range(len(numbers)):
        n = numbers[i]
        
        for j in numbers[i + 1 :]:
            if j > n:
                answer[i] = j
                break
    return answer

처음엔 직관적으로 numbers의 값을 차례로 가져오고 가여운 값 다음 인덱스부터 새로운 인덱스로 만들어 가져온 값과 비교했다

 

당연히 이중 for문을 사용했기 때문에 시간초과가 걸리지 않을까...? 했지만..

 

역시나..

 

시간이 오래 걸리기도 하고, 테스트 10번 이후로는 시간초과로 인해 대부분의 테스트 케이스를 실패하였다

두 번째 풀이

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

 

사실 처음에 stack을 이용한 풀이가 전혀 떠오르지 않아서 문제가 너무 어렵게 다가왔다..

 

[파이썬 PYTHON] 프로그래머스 【뒤에 있는 큰 수 찾기】

 

이 분의 풀이를 참고해서 문제를 이해해 보려고 노력했다..

 

먼저 풀이를 들어가기 전에 stack이라는 자료 구조에 대해 먼저 알아야 하는데 cs 공부를 하면서 많이 들어봤지만 그걸 또 적용하는 것은 다른 이야기더라..

 

stack은 데이터를 임시로 저장하는 자료구조로 문제에서 stack에 numbers의 index를 저장하고

 

만약 for문으로 불러온 numbers의 값이 stack의 마지막에 저장된 인덱스로 numbers를 조회한 값보다 크다면 answer의 값을 numbers의 값으로 바꾸는 건데..

 

내가 설명하고도 이해하기 어려운 것 같아서 예시를 들어서 설명을 하자면

numbers = [9, 1, 5, 3, 6, 2]

## 초기 설정
answer = [-1, -1, -1, -1, -1, -1] # -1을 numbers의 개수만큼, 나보다 큰 수가 없다면 -1을 저장
stack = [] # numbers의 index를 저장

## 첫 번째 사이클
n = numbers[0] # 9

# 1. stack의 길이가 0이기 때문에 while 종료
# 2. stack에 9의 index 저장
stack = [0]

## 두 번째 사이클
n = numbers[1] # 1

# 1. numbers[stack[-1]] == 9, 1은 9보다 작기 때문에 while 종료
# 2. stack에 1의 index 저장
stack = [0, 1]

## 세 번째 사이클
n = numbers[2] # 5

# 1. numbers[stack[-1]] == 1, 5는 1보다 크기 때문에
# 2. answer[stack.pop()] = 5
answer = [-1, 5, -1, -1, -1, -1]
# 3. numbers[stack[-1]] == 9, 5는 9보다 작기 때문에 while 종료
# 4. stack에 5의 index 저장
stack = [0, 2]

...

## 다섯 번째 사이클
n = numbers[4] # 6
stack = [0, 2, 3]

# 1. numbers[stack[-1]] == 3, 6는 3보다 크기 때문에
# 2. answer[stack.pop()] = 5
answer = [-1, 5, -1, 6, -1, -1]
stack = [0, 2]
# 3. answer[stack[-1]] == 5, 6은 5보다 크기 때문에
answer = [-1, 5, 6, 6, -1, -1]
stack = [0]
# 4. answer[stack[-1]] == 9, 6은 9보다 작기 때문에 while 종료
# 5. stack에 6의 index 저장
stack = [0]

 

이런 식으로 코드의 흐름이 흘러가게 된다

 

다음엔 더 잘해 보자!