프로그래머스 - 주식가격(Stack/Queue) / Level 2

문제 설명

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

 

제한사항

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

 

입출력 예시

prices	return
[1, 2, 3, 2, 3]	[4, 3, 1, 1, 0]

입출력 예 설명

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

 

풀이

def solution(prices):
    answer = []
    time = 0
    
    for i in range(len(prices)):  # 특정시점의 가격
        if i == len(prices)-1:  # 마지막 주식은 무조건 0을 return
            answer.append(time)
            break
            
        for j in range(i+1, len(prices)):  # 여러시점의 가격들과 비교
            if prices[j] >= prices[i]:  # 주식가격이 일정하거나 오르면 이어서 다음 시점과 비교
                time += 1
            else:  # 주식가격이 떨어졌으면 비교 중지하고 현재까지 소요시간 기록
                time += 1
                break
        
        answer.append(time)
        time = 0
    return answer

프로그래머스에서 푼 문제들 중에서 가장 빠르게 푼 문제였다.

처음에 문제를 볼 때는 무슨 말인지 잘 이해 안 되었지만 요점은 어느 한 시점의 주식 가격을 기준으로

몇 초 뒤에 가격이 떨어졌는지 기록하면 답이다.

 

따라서 이중 for문을 이용하면 쉽게 풀리는데

prices 리스트의 길이가 최대 10만이고 효율성 테스트가 있는 것을

보았을 때 아무 생각 없이 O(n^2)으로 풀면 안 된다.

 

어느 한 시점의 주식 가격이 정해졌을 때 과거의 주식 가격은 비교대상으로 삼을 필요가 없다.

위 사실을 기반으로 시간 복잡도를 낮춰주면 모든 효율성 테스트를 통과할 수 있다.