You Nicholas

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

1 분 소요

1. 문제

[level 2] 주식가격 - 42584

문제 링크

성능 요약

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

구분

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

채점결과


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

문제 설명

초 단위로 기록된 주식가격이 담긴 배열 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. 해결방법 시간복잡도

  1. 스택 O(N^2)

3. 문제 해결 및 코드

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

4. 알고리즘 및 해설

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

참고