프로그래머스 고득점 kit(유형정리) - 주식가격

코딩테스트 연습 - 주식가격 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

제한사항

• prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
• prices의 길이는 2 이상 100,000 이하입니다.

입출력 예pricesreturn

[1, 2, 3, 2, 3]

[4, 3, 1, 1, 0]

입출력 예 설명

• 1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.
• 2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.
• 3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것으로 봅니다.
• 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다.
• 5초 시점의 ₩3은 0초간 가격이 떨어지지 않았습니다.

 

 

문제는 매우 간단하다. 그냥 뒤에 더 큰 수만 없으면 안떨어진걸로 파악해버리면 그만이다.

 

사실 이중 for문을 사용해서 인덱스 비교를 해버리면 그만 아닌가? 라는 생각을 하기도 했지만, 스택/큐 문제이니 최대한 그쪽으로 접근을 하기로 했고 이중 for문을 사용할 시 O(n^2)으로 시간복잡도가 너무 커서 효율성 테스트를 통과하지 못할 거라는 생각으로 deque를 이용한 풀이를 생각해보았다. 다 풀고 나서 보니 이중 for문도 통과가 되긴 하더라.... 그리고 나랑 같은 풀이도 엄청 많아서 당황.....

 

 

※ 알고리즘

 

1. prices 배열을 deque로 묶어준다.

2. deque가 비지 않을 때 까지 while문으로 반복문 작업

3. 왼쪽 부터 popleft() 시켜주고 deque 안에서 p>i 되는 경우에는 주식 가격이 떨어지는 것이므로 break, 아니라면 계속해서 time변수를 높여준다.

4. answer 배열에 time 변수 값 담아주고 return 시켜주면 끝

 

from collections import deque

def solution(prices):
    answer = []
    dq = deque(prices)
    
    while dq:
        p = dq.popleft()
        time = 0
        
        for i in dq:
            time += 1
            if p > i:
                break
        answer.append(time)
        
    return answer

 

이렇게 deque를 활용해서 문제를 풀어보았다. 

 

※ Deque란?

 

- 파이썬 리스트와 같이 요소들을 담아주는 배열 형태

- 덱이라고 불리며 양방향 queue를 의미하여 앞, 뒤 모두에서 요소를 추가/제거 할 수 있다.

- 속도가 워낙 빨라서 list는 O(n) 이지만, deque는 O(1)의 시간복잡도를 가진다.

- popleft(), appendleft()의 형식으로 사용한다.

- 기존 list를 dq = deque(list)의 형식으로 선언 가능하다.

 

이 문제의 가장 최고 풀이는 stack을 사용한 것이 아닐까 싶다. 가장 시간복잡도 효율이 좋은 stack 풀이가 프로그래머스에 있어서 블로그에 가져와 보았다.

 

 

이 풀이인데 솔직히 봐도 잘 이해가 안 간다...... 왜 O(n)인지도...... 진짜 자료구조의 길은 멀고도 먼 것 같다 ㅠㅠㅠㅠㅠㅠ