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

문제 링크

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

생각의 흐름

1. 문제에 대한 이해
2. 코드로 구현

<문제 파악>

문제를 처음 읽었을 때, 너무 쉽다고 생각이 들었다. 그리고 아이디어를 바로 코드로 옮겨 적었고, 바로 통과했다. 하지만 효율성 테스트에서 시간이 조금 오래걸리는 느낌이 들었고, 다름 사람들의 풀이를 확인했다. 나는 출제자의 의도와 다르게 풀었다는 느낌이 들었다. O(N)으로 풀어야 할 문제를 O(N^2)로 풀었다. 스택을 사용하지 않았기 때문이다.

<코드로 구현하기>

포인트

1. 스택의 사용과 활용법

(스택 사용 X)

def solution(prices):
    answer =[]
    for i in range(len(prices)):
        j = i
        while j <len(prices):
            if prices[i]>prices[j]:
                j+=1
                break
            j+=1
        answer.append(j-i-1)
    return answer

(스택 사용 O)

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        while stack != [] and stack[-1][1] > prices[i]:
            past, _ = stack.pop()
            answer[past] = i - past
        stack.append([i, prices[i]])
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    return answer

스택을 사용해야 O(N)으로 풀 수 있다. 스택을 사용한 코드를 이해하기 힘들었다. prices에 있는 애들을 자신보다 작은 수를 만날 때까지 stack에 넣는다. 자신보다 작은 수를 만나면 위치의 차이만큼 answer를 수정한다. 마지막까지 stack에 남아있는 수들은 끝까지 감소하지 않은 것이므로 별도로 answer를 처리해준다.

후기

스택이 무엇이며 어떨 때 사용하는지 알았다고 스스로 생각했지만, 문제를 조금만 꼬아서 내도 이렇게 버벅거린다. 이 문제는 꼭 다시 풀어봐야 한다. 정답이 아닌 코드로 문제를 맞췄고, 다른 사람의 코드를 읽었으니 내 것이 아니다.