[Python : 프로그래머스] 주식가격

문제

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

풀이

def solution(prices):
    answer = [0]
    prices.reverse()
    print(prices)
    for i in range(1, len(prices)) :
        if prices[i] > prices[i-1] :
            answer.append(1)
        else :
            answer.append(answer[i-1]+1)
        
    return sorted(answer, reverse=True)

최초 접근했던 방법. 우선 말하자면 틀렸다.
접근했던 방법을 예제를 통해 설명하자면 아래와 같다.

input : [1, 3, 6, 0, 5, 2]
------------------------------------
[0]:2 --> 0 = 맨 처음 값은 무조건 0
[1]:5 --> 1 = 이전 값이 작으면 1
[2]:0 --> 2 = 이전 값이 크거나 같으면 + 1
[3]:6 --> 1 = 이전 값이 작으면 1
[4]:3 --> 2 = 이전 값이 크거나 같으면 + 1
[5]:1 --> 3 = 이전 값이 크거나 같으면 + 1
------------------------------------
output : [3, 2, 1, 2, 1, 0]
answer : [3, 2, 1, 2, 1, 0]

이 예제로만 확인했을 땐 아주 그럴듯하지만,
[2] 에 해당하는 0을 4로만 변경해도 바로 틀린다.

input : [1, 3, 6, 4, 5, 2]
------------------------------------
[0]:2 --> 0 = 맨 처음 값은 무조건 0       (O)
[1]:5 --> 1 = 이전 값이 작으면 1         (O)
[2]:4 --> 2 = 이전 값이 크거나 같으면 + 1  (O)
[3]:6 --> 1 = 이전 값이 작으면 1         (O)
[4]:3 --> 2 = 이전 값이 크거나 같으면 + 1  (X)
[5]:1 --> 3 = 이전 값이 크거나 같으면 + 1  (O)
------------------------------------
output : [3, 2, 1, 2, 1, 0]
answer : [5, 4, 1, 2, 1, 0]

완전히 잘못 접근했다.

이중루프를 이용하면 간단하겠지만 효율성 테스트에 걸릴 것 같아서
아예 이중루프는 배제하고 있었다.

그러다 70분 가까이 고민해도 도저히 답이 안보여서
에라 모르겠다 하고 이중루프로 짜서 제출해보니까 통과된다.
엥???

제출한 코드

def solution(prices):
    answer = []
    for i in range(len(prices)):
        sec = 0

        for j in range(i+1, len(prices)):
            sec += 1
            if prices[i] > prices[j]:
                break

        answer.append(day)

    return answer

효율성 테스트에 걸릴 것 같아서 배제했는데,
효율성 테스트를 모두 통과했다. 왜???

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

제한사항을 보고 이중루프를 돌려도 효율성에 문제가 없는 걸 알았어야했나?
계속 이중루프로 해결했다는 점에서 찜찜함이 남는다.

더 나은 풀이

def solution(prices):
    answer = [0] * len(prices)
    for i in range(len(prices)):
        for j in range(i+1, len(prices)):
            if prices[i] <= prices[j]:
                answer[i] += 1
            else:
                answer[i] += 1
                break
    return answer

가장 많은 좋아요를 받은 코드.
이중루프를 돌린 것은 똑같지만, 미리 answer 리스트 길이를 정해놓고
값을 더해주기만 했다. append 함수를 이용하는 것 보다 훨씬 빠를듯.
이런 단순한 문제에서도 기본기를 차이를 느끼게 되는구나.

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        c = prices.popleft()

        count = 0
        for i in prices:
            if c > i:
                count += 1
                break
            count += 1

        answer.append(count)

    return answer

스택을 사용한다는 취지에 가장 맞아보이는 코드
리스트를 덱으로 변환시키고, 앞에서부터 pop시킨다.
다만 개인적으로는 꼭 스택을 사용할게 아니라면
앞의 코드가 더 나아 보인다.