[프로그래머스] 주식가격 문제풀이 python

🐒 문제

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

✍ 나의 풀이

from collections import deque

def solution(prices):
    answer = []
    q = deque(prices)

    while q:
        count = 0
        now = q.popleft()
        
        for i in q:
            count += 1
            if i < now:
                break

        answer.append(count)

    return answer

스택 & 큐 카테고리의 문제이다.

깔끔하게 구현한거같아서 좋다 😊

---

🧠 문제 이해

처음 문제를 읽고 뭔 소린지 이해를 못해서 직접 손으로 써봤다.

prices 리스트의 왼쪽부터 순서대로 각 숫자가 몇 초 동안 가격하락이 없는지 출력해야하는 문제이다.

---

대체 답안(시간초과)

만약 deque를 통해 큐 자료구조를 사용하지 않고 코드를 짜면 어떻게 될까? 코드는 아래와 같을 것이다.

from collections import deque

def solution(prices):
    answer = []

    while prices:
        tmp = 0
        now = prices.pop(0)
        
        for i in prices:
            tmp += 1
            if i < now:
                break
            
        answer.append(tmp)

    return answer

정확성  테스트
테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.03ms, 10.2MB)
테스트 3 〉	통과 (0.30ms, 10.4MB)
테스트 4 〉	통과 (0.33ms, 10MB)
테스트 5 〉	통과 (0.63ms, 10.2MB)
테스트 6 〉	통과 (0.02ms, 9.97MB)
테스트 7 〉	통과 (0.20ms, 10.2MB)
테스트 8 〉	통과 (0.22ms, 10.3MB)
테스트 9 〉	통과 (0.03ms, 10.2MB)
테스트 10 〉	통과 (0.60ms, 10.2MB)

효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)

테스트 결과에 나오듯, 분명 문제에서 요구하는 코드는 맞으나 시간초과가 발생한다.

때문에 deque를 사용해야한다.

from collections import deque

def solution(prices):
    answer = []
    q = deque(prices) #prices 리스트를 q에 넣어 큐 자료구조로 사용

    while q: # q에 남은 요소가 있다면
        count = 0	# 몇 초동안 가격 하락이 없는지 세는 변수
        now = q.popleft()	# 가장 왼쪽요소 pop
        
        for i in q:	# 가장 왼쪽요소 다음부터 끝까지 돌면서
            count += 1	# 걸린 시간 +1
            if i < now:	# 가장 왼쪽요소보다 작은 숫자가 있으면
                break   # for문 탈출

        answer.append(count)	# 몇 초걸렸는지 append

    return answer

정확성  테스트
테스트 1 〉	통과 (0.00ms, 9.91MB)
테스트 2 〉	통과 (0.03ms, 10.1MB)
테스트 3 〉	통과 (0.27ms, 10MB)
테스트 4 〉	통과 (0.29ms, 10MB)
테스트 5 〉	통과 (0.59ms, 10.2MB)
테스트 6 〉	통과 (0.03ms, 9.81MB)
테스트 7 〉	통과 (0.31ms, 10MB)
테스트 8 〉	통과 (0.20ms, 10.2MB)
테스트 9 〉	통과 (0.02ms, 10.1MB)
테스트 10 〉	통과 (0.36ms, 9.98MB)

효율성  테스트
테스트 1 〉	통과 (59.04ms, 18.8MB)
테스트 2 〉	통과 (45.99ms, 17.6MB)
테스트 3 〉	통과 (74.19ms, 19.5MB)
테스트 4 〉	통과 (52.91ms, 18.2MB)
테스트 5 〉	통과 (35.24ms, 16.8MB)