PROGRAMMERS Python Lv2. 주식가격

이번 문제는 주식가격이다.

나의 코드는 다음과 같다.

def solution(prices):
    answer = []
    cnt = 0
    for idx in range(len(prices)):
        for j in range(1, len(prices)):
            if idx+j == 5:
                    break
            else:
                if prices[idx] <= prices[idx+j]:
                    cnt += 1
        answer.append(cnt)
        cnt = 0
    return answer

위의 코드로 1,2 테스트 중 1번만 통과하고 2번은 통과하지 못했다.
당연히 코드 제출 후 정확성과 효율성 점수에서도 0점짜리 코드였다.
내가 문제를 풀 때 고려했던 것은, for 문을 두 번 돌려서 각각의 원소들을
전부 비교하려 했다.

그렇지만, 대부분의 정답코드가 deque를 이용해서 풀었다.

from collections import deque
def solution(prices):
    queue = deque(prices)
    answer = []
    while queue:
        l = queue.popleft()
        cnt = 0
        for i in queue:
            if l > i:
                cnt += 1
                break
            else:
                cnt += 1
        answer.append(cnt)
    return answer

deque는 양 방향으로 처리할 수 있는 queue형 자료구조이다.
deque의 많은 함수들이 list 함수들과 동일한 역할을 수행한다.

deque를 사용하는 이유는 양끝 엘리먼트(element)에 접근하여
삽입 또는 제거를 할 경우, 일반적인 리스트(list)가 이러한 연산에

O(n)이 소요되는 데 반해, 데크(deque)는 O(1)로 접근 가능하다.
요악하자면, 양 끝 원소에 대한 append와 pop의 속도가 월등히 빠르다.

위의 코드를 풀이하자면, 우선 리스트인 prices를 데크로 만들어준다.

queue의 왼쪽부터 popleft를 통해 추출 및 제거를 동시에 해준다.

for문을 통해 남은 원소들과의 대수비교를 해준다.

1의 경우, 끝까지 작기 때문에 cnt는 4까지 누적된다.

이를 while문을 통해 queue의 마지막 원소가 popleft될 때까지 수행한다.

이번 문제를 통해 데크의 기능에 대해 처음 알았고, 속도에 대한 고민을 해보게 되었다.