[Programmers / Level2] 뒤에 있는 큰 수 찾기 + 주식가격

 

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

프로그래머스

---

<내코드>

 

결론부터 말하자면, 스텍인덱스를 활용해서 푸는 문제이다. 아래와 같이 제한사항이 걸려있는 상황이다.

 

제한사항

4 ≤ numbers의 길이 ≤ 1,000,000

 

제한사항에 따르면 1000000번 + @의 연산을 한다. 따라서 아래와 같이 포문 두번 돌리는 O(N**2)연산을 하면 실패한다..

 

<내코드>  - 오답코드

def solution(numbers):
    total_numbers = len(numbers)
    answer = [-1] * total_numbers
    for i in range(total_numbers):
        for j in range(i, total_numbers):
            if numbers[i] < numbers[j]:
                answer[i] = numbers[j]
                break

    return answer

 

 

처음에 생각안하고 짠 O(N**2) 의 코드이다..

 

그러면 어떻게 해야할까?

 

logN의 수행시간을 나타내는 힙은 비선형적인 구조이기에 이문제에서 사용은 어렵다!

 

선형적인 자료구조를 써야하는데 그럼 스택 또는 덱을 써야겠다고 생각했다.

 

아래와 같이 스택의 top에 있는 숫자를 보고 서로 비교하는 과정을 거치며 구현해주자

출처: https://sasca37.tistory.com/306

<정해코드>

def solution(numbers):
    stack = []
    answer = [0 for _ in range(len(numbers))]
    
    for idx, num in enumerate(numbers):
        while stack and numbers[stack[-1]]:
            if num > numbers[stack[-1]]:
                k = stack.pop()
                answer[k] = num
            else: break
        stack.append(idx)
        
    for i in stack:
        answer[i] = -1
        
    return answer

 

 

아래는 스택을 이용하여 동일한로직의 문제여서 가지고왔다.

 

---

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

프로그래머스

 

<정해코드>

def solution(prices):
    stack = []
    answer = [0 for _ in range(len(prices))]
    for i, price in enumerate(prices):
        while stack and prices[stack[-1]] > price:
            val = stack.pop()
            answer[val] = i - val
        stack.append(i)
    
    for j in stack:
        answer[j] = i - j
    
    return answer

 

위와 동일하게 스택에다 집어넣고, 서로비교한다.

마지막으로 스택에 남아있는 값을 인덱스 설정을 해주면 끝!