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

문제

출처: 프로그래머스

---

풀이

이중포문을 활용해서 풀 수 있을테지만 효율성 테스트에서 걸릴 것 같았다. 스택을 사용해서 풀어보려고 했는데

문법도 잘 모르고 로직도 확실하지 않은데 풀다가 짜증날 것 같았다.

그래서 돌아가는 길이 가장 빠른 길이라고 먼저 이중포문으로 대강 풀어보았다. 그런데 웬일,, 효율성 테스트까지 그냥 통과해버림

def solution(prices):
    answer = []
    
    for i in range(0, len(prices)):
        flag = False
        for j in range(i + 1, len(prices)):
            if prices[i] > prices[j]:
                answer.append(j - i)
                flag = True
                break;
        if flag == False:
            answer.append(len(prices) - i - 1)
    
    return answer

그렇지만 절대 이 풀이를 의도한 것 같진 않아 다른사람의 풀이를 보기 전에 다른 방식으로 풀어보기로 했다.

 

미완성 코드인데 디버깅하려하니 자꾸 프로그래머스 서버 응답이 안된다해서 접었다.

생각한 로직은 다음과 같다.

 

1. answer을 price의 길이만큼 -1로 초기화하고 첫 주식 가격을 스택에 넣는다.

2.  for문을 돌며 바로 전 스택의 주식 가격보다 현재 주식의 가격이 높으면 (상승주가면) 스택에 추가하고 넘어간다.

3. 주가가 떨어졌을 경우 스택의 top 가격이 현재 가격보다 낮거나 같아질 때까지(주가가 떨어진 시점까지) pop 하며 답을 저장한다. 예시의 경우로 보자면, 

price = [1, 2, 3, 2, 3]

i = 3일 때

stack = [1, 2, 4]

answer = [-1, -1, 1, -1, -1] 이 된다.

4. 마지막까지 떨어지지 않은 경우를 저장해 준다.(미구현)

def solution(prices):
    answer = [-1 for i in range(prices)]
    stack = []
    
    stack.append(0)
    for i in range(1, len(prices)):
        if prices[i] > prices[stack[-1]]:
            stack.append(i)
        else:
            for j in range(len(stack) - 1 ,-1, -1):
                if prices[stack[j]] > prices[i]:
                    answer[stack[j]] = stack.pop()
                    j -= 1
                else:
                    stack.append(i)
                    break
    
    return answer

맞는 로직인지 모르겠다. 다른 사람의 코드를 보면서 확인해보도록 하겠다.

---

다른 사람의 코드

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

이중포문을 활용한 나의 처음 로직과 유사하지만 코드는 좀 더 깔끔하다.

 

스택을 활용한 코드는 다음과 같다. 

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

deque 라는 것을 사용했는데, 이것은 double-ended-queue의 줄임말이며 양 끝단에서 접근 가능한 큐다.

list에도 큐처럼 사용할 수 있는 append, pop 메소드가 있어 둘의 차이를 알아봤다.

 

1. list

- 삽입/삭제 O(1)

- 배열의 크기가 변할 때, index가 작은 위치에 삽입/삭제가 이루어질 때 비효율적

2. deque

- 삽입/삭제 O(1)

- 양 끝단에 접근 가능

- 가운데 부분을 찾거나 삽입/삭제 시 비효율적

 

따라서 이번 문제는 deque를 사용하는 것이 좀 더 효율적이라 할 수 있다.

 

다시 본론으로 돌아가서 해석해보았는데, 이중포문을 사용한 코드와 로직의 차이가 없었다. 내가 생각한 스텍의 사용 방법이 아니었다.

 

다른 코드를 찾아봤다.

def solution(p):
    ans = [0] * len(p)
    stack = [0]
    for i in range(1, len(p)):
        if p[i] < p[stack[-1]]:
            for j in stack[::-1]:
                if p[i] < p[j]:
                    ans[j] = i-j
                    stack.remove(j)
                else:
                    break
        stack.append(i)
    for i in range(0, len(stack)-1):
        ans[stack[i]] = len(p) - stack[i] - 1
    return ans

내가 생각한 방식대로 푼 코드였다.

여기도 이중 for문이지만 스택 내부에서 거꾸로 돌기 때문에 평균적으로 O(n^2)은 나오지 않을 것이다.

물론 기존 코드도 index가 커질수록 두번째 포문을 덜 돌 확률이 커 O(n^2)까지는 안 나오겠지만, 이 코드는 아직 주가가 떨어지지 않은 값들만 확인하기 때문에 가장 효율적일 것이다.

생각한 방법이 옳아 기분이 좋다ㅎㅎ

예상대로 기존 코드보다 확연히 줄어든 시간을 볼 수 있었다.

 

출처: daimhada.tistory.com/56