42584: 주식가격[스택/큐]

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

---

1. 문제

• 초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.
  
  제한사항
  
  prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
  prices의 길이는 2 이상 100,000 이하입니다.

 

---

2. 문제의 조건

• 1 <= prices <= 10,000
• 2 <= prices_length <= 100,000

 

---

3. 문제 접근

• 시간 복잡도
  
  추후 보강

 

• 아이디어
  
  stack을 이용하는 문제이지만, 더 쉬운 풀이 방법이 생각나서 메모이제이션 기법을 사용하였습니다.
  [1, 2, 3, 2, 3]을 기준으로 idx가 4인 3은 항상 시간초간 떨어지지 않습니다.
  그럼 우리는 주어진 5 - 1 개의 길이만 계산하면됩니다.
  만약 idx가 0인 1을 기준으로, 다음 2가 되기 직전인 [1, 2, 3] 3초 동안 가격이 떨어지지 않았습니다.
  그다음 idx가 1인 2는 [2, 3] 인 2초 동안 가격이 떨어지지 않습니다.
  그다음 idx가 2인 3은 []인 0초 동안 가격이 떨어지지 않습니다.
  idx가 3인 2는 []인 0초 동안 가격이 떨어지지 않습니다.
  
  이처럼 떨어지기 직전 까지의 값을 구한 뒤, 각 떨어질때 + 1초를 모두 더해준 뒤 마지막인 시간초인 0초를 추가해주시면 됩니다.

 

---

4. 풀이 방법

• i가 0번째 부터 for문을 반복합니다.
• p(point)가 i + 1 번째 부터 for문을 반복합니다.
  [1,2,3,2,3]일 경우 1과 2~를 떨어지는 순간까지를 비교해야하기 때문
• 만약 현재의 i번째의 가격이 p번쨰의 가격보다 같거나 작으면 가격이 떨어지는 것은 아니므로 stack[i]에 1씩 더해줍니다.
  만약 prices[i]가 크다면 주식이 떨어 진 것이므로 break로 중단합니다.
• 현재까지 계산한 for문을 끝내면, 떨어진 시간초는 포함하지 않았으므로 각각 1초 씩 더해줍니다.
• 마지막 시간은 떨어지는 시간이 항상 0초이므로 0을 추가해줍니다.

 

---

5. 소스코드

• cjw-git.tistory.com/90

 

---

 

cjw.git@gmail.com