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

문제출처

1. 문제

문제 설명

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

2. 풀이

처음에 map()과 slice(), findIndex()를 사용해서 풀었더니 정확성은 통과했지만 유효성에서 시간초과가 발생했다.

// 정확성은 통과했지만 유효성은 통과 X
function solution(prices) {
  return prices.map((ele, idx) => {
    return (
      prices.slice(idx + 1).findIndex((e) => e < ele) + 1 ||
      prices.length - (idx + 1)
    );
  });
}

slice()를 사용해서 각 원소마다 새로운 배열을 생성했기 때문에 메모리 사용량이 증가했다. 또한 최적화없이 findIndex()를 사용하여 각 원소마다 순회를 하였기 때문에 불필요한 순회가 발생하였다.

따라서 더 효율적인 코드로 수정했다.

for문을 돌면서 각 원소마다 초기 값을 1로 할당했다.
현재 원소가 바로 다음 원소 이하라면 그 이후 원소들을 순회하면서 주가가 떨어지는 시점을 찾았다. 떨어지는 시점을 발견하면 순회를 중지했다.

// 정확성, 유효성 모두 통과한 코드
function solution(prices) {
  let ans = new Array(prices.length).fill(0);

  for (let i = 0; i < prices.length - 1; i++) {
    ans[i] = 1;
    
    // 다음 주식 가격이 현재 주식 가격 이상이라면
    // 현재 주식보다 가격이 작을 때까지 count하기
    if (prices[i] <= prices[i + 1]) {
      for (let j = i + 1; j < prices.length - 1; j++) {
        if (prices[i] > prices[j]) break;
        else ans[i] += 1;
      }
    }
  }
  
  return ans;
}

문제는 stack으로 푸는 것을 의도했지만 stack으로 잘 풀리지가 않아서 익숙한 방법으로 풀었다. stack을 더 공부해서 다시 풀어봐야겠다.