프로그래머스 / 스택 / 뒤에 있는 큰 수

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

뒤에 있는 숫자 중에서 나보다 큰 가장 가까운 수를 찾아야 된다.

 

해당 알고리즘은 굉장히 알려진 알고리즘이다.

스택 알고리즘 중 boj에 오큰수라고 한다.

boj.ma/17298/t

 

input	output
[1, 2, 3, 4, 5, 6]	[2, 3, 4, 5, 6, -1]

 

단순하게 오른쪽에 나보다 큰 수가 있으면 그 큰수를 넣어주면 된다.

근데 만약 다음과 같은 예시라면

input	output
[1, 1, 2, 2, 3, 3, 4]	[2, 2, 3, 3, 4, 4, -1]

 

1이라는 값이 여러 개일 수도 있다는 것을 알고 있어야 한다.

 

결국 다음과 같은 로직으로 풀이를 진행하면 된다.

 

1. 스택에 처음 numbers 값을 넣는다.

2. for문을 1번 인덱스부터 돌리기 시작한다.

3. for문을 돌면서 현재 for문이 가리키고 있는 값과 스택의 top 값을 비교한다.

3-1. top값이 작다면 현재 for문이 가리키고 있는 값이 "뒤에 있는 큰 수" 이기 때문에 스택의 값을 뺀다.

4. 현재 for문이 가리키고 있는 값을 스택에 넣는다.

 

 

 

정답코드

---

'''
'25. 10. 5.(일)
1. 정수가 있고, 배열의 각 언소들에 대해 자신보다 뒤에 있는 숫자 중
자신봐 크면서 가장 가까이 있는 수를 뒷 큰수
2. 뒤에 있는 수인데, 가장가까운 수

stack을 이용해서 만들기

1. 첫 번째 수를 넣기
2. stack의 top이 현재 보고 있는 숫자보다 작다면 배열에 넣어준다.
'''
def solution(numbers):
    answer = [-1] * len(numbers)
    s = [[numbers[0], 0]]#stack
    
    for i in range(1, len(numbers)):
        value = numbers[i]
        #value
        while s and s[-1][0] < value:
            v, idx = s.pop()
            answer[idx] = value
        
        s.append((value, i))
    return answer

 

깃허브 : https://buly.kr/2qZD08x

유튜브 : https://youtu.be/7eV17e2GHmc