[Programmers] 주식 가격

https://school.programmers.co.kr/learn/courses/30/lessons/42584?language=javascript

프로그래머스

이 문제는 시간초과를 생각해야 하는 문제다.

prices의 길이가 10만이기 때문에 반복문을 2번만 해도 O(n^2)이기 때문에 시간 초과가 걸린다.

따라서 O(n^2)로 풀면서 break를 잘 쓰거나 더 나은 O(n) 방법으로 해야 한다.

 

O(n^2) 방법

function solution(prices) {
    let answer = [];
    for (let i = 0; i < prices.length; i++) {
        let count = 0;
        for (let j = i; j < prices.length - 1; j++) {
            if (prices[i] <= prices[j]) {
                count++;
            } else {
                break;
            }
        }
        answer.push(count);
    }
    return answer;
}

O(n^2) 방법은 크게 어려울 것이 없다. 반복문을 두 번 돌려 값이 낮아지면 break 하고 값이 높아지면 count를 높인 다음 answer에 넣어 리턴하면 된다. 하지만 이 방법의 최악은 n^2 반복이 될 수 있다.

 

O(n) 방법

function solution(prices){
  const n = prices.length;
  const answer = new Array(n).fill(0);
  const stack = [0];

  for(let i = 1 ; i < n; i++) {
    while (stack.length > 0 && prices[i] < prices[stack[stack.length - 1]]) {
      const top = stack.pop();
      answer[top] = i - top;
    }

    stack.push(i);
  }
  while(stack.length > 0){
    const top = stack.pop();
    answer[top] = n - 1 - top;
  }
  return answer;
}

O(n) 방법은 한 번의 순회로 값을 저장하는 것이다.

이 문제를 간단하게 생각하면 현재의 값이 바로 이전의 값보다 작으면 1초가 유지됐었으므로 값을 확정시켜 이후의 계산에서 제외하면 된다.

즉 불필요한 연산을 줄여 시간복잡도를 최소화시키는 것이다.

 

구현 방식은 다음과 같다.

1. prices의 길이만큼 answer배열을 만들고 스택에 미리 첫 번째 인덱스(0)를 넣어둔다.

2. 반복문을 통해 현재 값과 바로 이전의 값을 비교하여 가격이 떨어졌다면 pop을 진행한 뒤 해당 인덱스 answer에 1의 값을 확정시킨다.

3. 값이 떨어지지 않았으면 stack에 인덱스를 저장한다.

4. 스택의 인덱스들을 pop 하여 prices길이에서 빼면 값을 유지한 기간이 나오므로 해당 인덱스 answer에 저장한다.

 

시간복잡도를 생각 안 하고 풀면 간단하게 풀 수 있고 break를 잘 써도 간단하게 풀 수 있는 문제이지만, stack에 관련된 문제이기도 하고 시간복잡도를 줄이며 푸는 것이 정석이므로 목적성에 맞게 푸는 게 맞는 거 같다.