You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

1 분 소요

1. 문제Permalink

[level 2] 주식가격 - 42584Permalink

문제 링크

성능 요약Permalink

메모리: 16.8 MB, 시간: 18.44 ms

구분Permalink

코딩테스트 연습 > 스택／큐

채점결과Permalink


정확성: 66.7
효율성: 33.3
합계: 100.0 / 100.0

문제 설명Permalink

초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않았습니다.

※ 공지 - 2019년 2월 28일 지문이 리뉴얼되었습니다.

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

2. 해결방법 시간복잡도Permalink

  1. 스택 O(N^2)

3. 문제 해결 및 코드Permalink

def solution(prices):
# 반복문이 도는 동안 1초씩 증가함
n = len(prices)
result = [0] * n
stack = []
for idx, price in enumerate(prices):
while len(stack) != 0 and price < prices[stack[-1]]:
tmp = stack.pop()
result[tmp] = idx - tmp
stack.append(idx)
while len(stack) != 0:
tmp = stack.pop()
result[tmp] = n - 1 - tmp
return result
view raw 42584.py hosted with ❤ by GitHub

  • 주석을 참고하면서 이해를 돕습니다.Permalink

4. 알고리즘 및 해설Permalink

  1. 이중 반복문을 통해서 해당 문제에 나오는 시점과 가격을 조건에 맞게 구하면 된다.
  2. 입력값과 같은 길이의 0으로 가득찬 배열을 만들어준다.
    • 반복문을 통해서 입력값을 인덱스와 값으로 받아준다.
      • 만약 스택에 적재된 값이 없으면 인덱스 값을 넣어준다. (처음 시점을 알기 위해서)
      • 만약 스택에 이미 쌓여져있고, 스택에 쌓여진 시점의 시세가 현 시세보다 크다면(시세가 하락했다면) 스택에서 해당 값을 빼주고, 결과값에 현재 시점 - 뺀 시점을 해준다.
  3. 반복문 이후에 만약 스택이 비어있지않다면, 스택을 비우면서 결과에 전체 길이 - 1 - 뺀 시점을 해준다.
    • -1을 해주는 이유는 모든 PRICE는 1 이상이므로 1은 더 이상 떨어지지 않기 때문이다.
  4. 최종 결과물을 출력해준다.

참고