[프로그래머스/Lv2] 주식가격

문제

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 반환하는 함수를 만들어야 한다.

 

 

제한사항

1. prices의 각 가격은 1 이상 10,000 이하인 자연수이다.

2. prices의 길이는 2 이상 100,000 이하이다.

 

 

코드

def solution(prices):
    reversed_prices = list(reversed(prices))

    answer = []
    while len(reversed_prices) != 0:
        tmp  = reversed_prices.pop()
        check = 0
        for price in reversed(reversed_prices):
            if price < tmp:
                check += 1
                break
            else:
                check += 1
        answer.append(check)

    return answer

 

 

설명

이 문제는 프로그래머스에서 제공하는 문제설명과 입출력 예시를 보지말고,

바로 구글에 해당 문제를 검색하거나 질문하기 탭을 눌러서 문제 해설을 보자.

 

지문만으로 문제를 이해하기 너무 난해하기 때문에 시간낭비하지 말고 문제 해설을 보는 것을 추천한다.

 

예시로 문제를 설명한다.

[1, 2, 3, 2, 3] 배열이 있을 때,

첫 번째 인덱스값 1은 2, 3, 2, 3 까지 가격이 떨어지지 않았기 때문에 결과값 4을 반환한다.

두 번째 인덱스값 2는 3, 2, 3 까지 가격이 떨어지지 않았기 때문에 결과값 3을 반환한다.

세 번째 인덱스값 3은 2에서 가격이 떨어지기 때문에 결과값 1을 반환한다.

네 번째 인덱스값 2는 3까지 가격이 떨어지지 않았기 때문에 결과값 1을 반환한다.

다섯 번째 인덱스값 3은 마지막 인덱스이기 때문에 계산할 필요 없이 0을 반환한다.

 

문제를 이해했으면 여러가지 방법으로 문제를 풀 수 있다.

문제 분류는 스택/큐라고 되어있는데, 솔직히 잘 모르겠다.

어떻게 풀어도 시간복잡도가 좋지 않게 나와서 굳이 스택/큐로 풀지 않아도 될 것 같다.

 

reversed_prices = list(reversed(prices))

pop의 시간복잡도를 줄이기 위해 prices 배열을 반전시켜 reversed_prices에 저장한다.

 

while len(reversed_prices) != 0:
    tmp  = reversed_prices.pop()
    check = 0
    for price in reversed(reversed_prices):
        if price < tmp:
            check += 1
            break
        else:
            check += 1
    answer.append(check)

reversed_prices의 길이가 0이 아닐 때 까지 반복한다.

reversed_prices의 마지막 원소를 pop하여 tmp에 저장한다.

check는 가격이 떨어지지 않는 동안의 초를 계산하여 저장할 변수이다.

 

reversed_prices의 원소들을 거꾸로 꺼내며(price) 반복한다.

만약 price이 tmp보다 작으면 check를 1더하고 반복문을 종료한다.(가격이 떨어지는 시점)

그렇지 않으면 check를 1더하고 반복한다.

 

안쪽 반복이 끝나면 answer에 check를 append한다.

 

return answer

 

answer를 반환한다.

 

 

이 코드를 제출하기 전에 효율성에서 통과하지 못한 코드가 있는데

def solution(prices):
    answer = []
    
    for i in range(len(prices)):
        check = 0
        for num in prices[i+1:]:
            if prices[i] > num:
                check += 1
                break
            else:
                check += 1 
        answer.append(check)

    return answer

내가 생각하기엔 이 코드도 최악의 경우 시간복잡도가 O(N^2)이고

통과한 코드도 최악의 경우 시간복잡도가 O(N^2)인데

왜 위 코드는 통과하고 아래 코드는 통과 못했는지 이해가 잘 안간다.

 

이 문제에 시간을 너무 쓰지 말고 적당한 선에서 다른 사람이 푼 문제 풀이를 보고 넘어가는 것을 추천한다.