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

진짜 너무 어려웠다..

 

문제를 겨우 이해해봤고 내가 이해한 바탕으로 예제를 통해 설명해보겠다.

 

stack을 사용할 것이고, stack에는 값이 아닌 인덱스를 갱신해 나갈 것이다.

먼저 첫번째 원소(index = 0)인 9는 비교대상이 없으므로 stack에 그냥 입력한다.

 

stack에 index가 아직 존재한다는 뜻은 아직 뒷 큰수를 만나지 못했다는 의미이다.

 

 

 

그 다음 두번째 원소(index = 1)은 값이 1이고 stack을 확인해서 뒷 큰 수로서 역할을 할 수 있는지 확인해본다.

 

하지만 stack에 저장되어 있는 인덱스로 값을 확인해보니 1보다 큰 9이므로 소거할 수 없다.

 

stack에 변화 없이 index 1을 스택에 추가한다.

 

 

 

그 다음 3번째 원소인 (index = 2) 5가 뒷 큰 수 역할을 할 수 있는지 확인해본다.

 

stack[-1] 원소가 1이고 1이 가리키는 값은 1로 5는 1의 뒷 큰 수 역할을 할 수 있다.

따라서 answer[1]에 5를 기록한다.

그리고 stack.pop()을 통해 뒷 큰 수를 채웠으니 인덱스 1을 지운다.

 

그러면 stack = [0] 인 상황이 되는데

 

5가 뒷 큰 수 역할을 할 수 있는지 확인해본다.

하지만, 0이 가리키는 값은 9이므로 5는 뒷 큰 수 역할을 할 수 없어 0을 소거할 순 없다.

 

따라서, index = 2를 stack에 추가하고 다음 단계로 넘어간다.

 

 

 

 

 

4번째 원소인(index = 3) 3이 뒷 큰 수 역할을 할 수 있는지 확인해본다.

 

stack[-1] 인 2가 가리키는 원소는 5이므로 3은 뒷 큰 수 역할을 할 수 없고 stack에 아무런 영향을 주지 못하고

stack에 index = 3을 추가하고 다음 단계로 넘어간다.

 

 

 

 

 

5번째 원소인 (index = 4) 6이 뒷 큰 수 역할을 할 수 있는지 확인해본다.

 

먼저 stack[-1]인 3이 가리키는 원소가 3이므로 6은 뒷 큰 수 역할을 할 수 있으므로

answer[stack[-1]] = answer[3] 에 6을 기록한다.

그리고 stack.pop()을 통해서 뒷 큰 수를 기록한 인덱스를 stack에서 제외시킨다.

 

한 번더 확인해본다.

stack[-1]인 2가 가리키는 원소가 5이므로 6이 뒷 큰 수 역할을 할 수 있으므로 마찬가지로 

answer[stack[-1]] = answer[2] 에 6을 기록한다.

 

한 번더 확인해본다.

stack[-1]인 0이 가리키는 원소가 9이므로 6은 뒷 큰 수 역할을 할 수 없고 

stack에 index = 4를 추가하고 다음 단계로 넘어간다.

 

 

......

 

 

이런식으로 진행 되는 로직이고, 이를 코드로 구현하면 다음과 같다.

 

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

 

최대한 잘 설명해보려고 노력했는데.. 설명한 내용이 잘 전달됐으면 좋겠다..ㅎ