[프로그래머스 Level 2] 주식가격 / (스택/큐) / 파이썬

 

<문제>

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

 

<풀이>

def solution2(prices: list):
    answer = []
    
    ##1
    price = prices[::-1]
    time = 0
    delay = price.copy()
    _ = delay.pop()
    
    ##2
    while len(delay) > 0:
        time += 1
        now = price.pop()
        later = delay.pop()
        # print(now, price)
        # print(later, delay)
		
        if now > later:
            ## 3-1
            answer.append(1)
        else:
            ## 3-2
            flag = False
            for i in range(1, len(price)):
                if now > price[-i - 1]:
                    flag = True
                    answer.append(i + 1)
                    break
            if not flag:
                answer.append(len(price))
        # print(answer)
        # print('*' * 20)
    answer.append(0)
    # print(answer)
    return answer

 

코드 설명:

 

## 1:

스택/큐 구조를 이용하기 위해 우선 prices를 뒤집은 배열을 price로 두었다. delay라는 배열을 만들었는데 문제 조건에 따라 주식 가격을 비교하려면 우선은 연속한 값 2개를 비교하는 과정이 필요하기 때문. pop()을 써서 시간효율성을 좋게 만들려고 하다보니 코드의 복잡함과 메모리를 좀 더 잡아먹게 된 듯하다.

 

## 2:

delay가 price보다 한 개 적다보니 에러나는 것을 막기 위해 delay의 길이를 기준으로 while문 loop를 돌렸다. time은 loop가 어떻게 돌아가나 확인차 만든 변수라서 없어도 지장은 없다. 

 

## 3:

현재 값이 그 다음 값보다 크면 주식이 바로 떨어지는 것으로 answer에 1을 추가한다. 

 

만약 반대의 경우면 for문으로 그 다음 값들을 탐색한다. 탐색하다가 현재 값보다 작은 값이 발견되면 break 한다. 만약 발견되지 않고 탐색이 끝나면 현재 값이 가장 작은 값이므로 flag가 바뀌지 않는다. 이 경우를 대비해서 if문을 넣어주었다.

 

이 코드가 효율성 측면에서 좀 더 좋은 이유는 pop으로 인해 3-2에 해당하는 경우가 생길 시 탐색하는 배열의 길이가 점점 작아지기 때문이다.

 

+@

스택/큐를 이용하긴 했지만 3-2의 케이스에 해당하는 경우를 더 효과적으로 풀면 시간이 더 줄일 수 있을 것이다. 개인적으로 O(N)까지는 아니고 O(NlogN)정도 되는 것 같다.

 

+@

다른 사람들의 풀이에 보면 가장 짧으면서 사람들이 많이 푼 코드가 바로

 

 

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

 

이 코드인데... 

O(N^2)에 가깝다. 효율성 테스트에서 통과는 하지만 스택/큐를 이용했다고 보기도 힘들다.

 

본인 코드의 효율성

for문 2번 사용시 효율성

for문으로만 탐색하기 때문에 배열의 길이가 문제에서 주어진 그대로 쓰므로 조건문에서 break를 쓴다해도 전체적인 탐색 수는 상당히 많은 편이기 때문이라 할 수 있다.