[프로그래머스] 주식가격 (javascript)

https://school.programmers.co.kr/learn/courses/30/lessons/42584

프로그래머스

 

🤔 해결방법

1. 첫 번째 for문에서 주식 가격 배열 prices를 처음부터 끝까지 순회하며 주식이 떨어지지 않은 시간 time을 0으로 초기화
2. 두 번째 for문에서 현재 주식 가격보다 뒤에 있는 주식 가격들을 순회하며 time 변수를 1씩 증가
3. 만약 현재 주식 가격이 다음 주식 가격보다 높다면 break로 빠져나오고 time을 answer에 push
4. 위의 과정을 반복하며 answer를 반환

 

 

🔑 풀이

먼저 이 문제는 현재 시점에서 처음으로 주식이 떨어진 시점까지의 유지시간을 차례로 구해야한다.

스택/큐 문제인만큼 shift와 push를 사용했다.

 

function solution(prices) {
    let answer = [];

    while (prices.length > 0) {
      let first = prices.shift();
      let time = 0;

      for (let i = 0; i < prices.length; i++) {
        time++;
        if (first > prices[i]) break;
      }
      answer.push(time);
    }
    return answer;
  }

 

prices에서 shift로 맨 앞 요소를 first에 넣고 나머지 요소들과 비교하며 time을 하나씩 증가시킨다.

더 작은 요소가 있다면 break로 for문을 빠져나오고 그 때까지의 time을 answer에 push한다.

그런데 정확성 테스트는 모두 통과했지만 효율성 테스트에서 1개만 빼고 모두 실패였다.😥

 

어떻게 더 효율적인 코드를 만들 수 있을지 모르겠어서 구글링을 했다.

그냥 단순한 이중 for문으로 효율성 테스트까지 통과한 분들이 있어 나도 이중 for문 풀이로 바꿔보았는데 모두 통과했다.

function solution(prices) {
    const answer = [];

    for (let i = 0; i < prices.length; i++) {
      let time = 0; 

      for (let j = i + 1; j < prices.length; j++) {
        time++;

        if (prices[i] > prices[j]) {
          break;
        }
      }
      answer.push(time); 
    }
    return answer;
  }

 

왜 shift를 사용한 풀이보다 단순 이중 for문이 더 효율적인지 생각해봤다.🤔

일단 두 개의 풀이 모두 시간 복잡도는 O(n^2)이다.

그런데 첫 번째 풀이는 shift를 사용해서 첫 번째 요소를 제거하고 배열을 지속적으로 업데이트 시키는 부분이 있다.

따라서 O(n)의 추가시간이 더 있다.

하지만 그냥 이중 for문으로 배열만 순회하는 두 번째 풀이는 배열의 변화 없이 그대로 사용하고 인덱스에 직접 접근하기 때문에 메모리를 비교적 덜 사용한다고 볼 수 있다. 추가시간도 O(1)이겠다.

따라서 두 번째 풀이가 더 빠를 수 있다는 생각이 들었다..!