[프로그래머스]주식가격-스택/큐

문제 설명

 

def solution(prices):
    answer = []
              
    for i in range(len(prices)):
        cnt = 0
        for j in range(i+1, len(prices)):
            cnt += 1
            if prices[i] > prices[j]: # 가격이 떨어짐을 의미
                break
        
        answer.append(cnt)
            
    return answer

 

코드 설명

첫번째 반복문에서는 prices 리스트의 길이만큼 반복한다. 카운트를 위한 변수를 0으로 초기화 한다. 다음 반복문은 i+1 부터 시작하여 prices 리스트의 길이만큼 반복한다. 만약 prices[i] > prices[j] (즉, 가격이 떨어졌다면) break를 통해 두번째 반복문을 탈출한다.

그렇지 않다면 (즉, 가격이 떨어진 적이 없다면) 반복문을 수행한 수만큼의 cnt 를 answer 리스트에 넣어준다.

 

Point : 이 문제는 스택이나 큐를 활용하지 않고도 이중 포문을 활용하여 풀 수 있다. (단, 시간 복잡도는 높아지게 된다) 

현재 주식 가격 i 와 다음에 등장하는 주식 가격 j 의 관계를 파악한다. i > j 가 될 경우 가격이 떨어지는 것을 의미 하므로 그 즉시 두번째 반복문을 탈출하도록 한다. cnt 는 가격이 떨어지기 전까지 1초씩 증가시키게 된다. 두번째 반복문이 끝난 후 cnt 값을 answer 리스트에 넣어주면 된다.