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

January 23, 2024

📖 문제

level2 주식가격

✏️ 나의 풀이

문제 푸는 것보다 문제 해석이 더 어려웠던 문제다.

IMG_F9CB8D800D00-1

이해할려고 손으로 하나하나 작성했다…

이 문제는 가격이 떨어지지 않은 기간이 몇 초인지 구하는 문제이다.
여기서 의문이 들었던게 떨어지지 않은 기간이 몇초인가 이 문장이 모호했다.
만일, [4, 5, 1, 2, 6, 1, 1] 일경우
0번째 인덱스를 기준으로 보았을때 4보다 작은 갯수를 구하는 문제로 착각했던 것이다.
그래서 0번째 인덱스의 값이 3이라고 생각했다.
- 하지만 위 예시의 답은 [2, 1, 4, 2, 1, 1, 0]
물론 이렇게 생각해서 바로 풀지는 않았다. 이 생각도 뭔가 이상하다는 느낌이 강해서 문제를 뚫어져라 쳐다봤다.
- 입출력 예시 [1, 2, 3, 2, 3]에서 2번째 인덱스가 2로 되면 위 생각이 완벽한거 같은데…
결론적으로 문제에 최초라는 단어 하나만 추가되면 오해 없이 풀 수 있는 문제였던 것 같다.
최초로 떨어지는 기간이 몇초인지를 구하라는 문제였으면 이렇게까지 고민하지 않고 바로 풀 수 있었을 것같다.
가격이 떨어진 후부터는 더 이상 계산하지 않으면 된거였다!

코드 설명

변수 선언

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

answer: 정답을 담을 배열
stack: 매개변수인 prices를 담으며, 비교할 배열

stack 로직

prices.forEach((price, index) => {
    if (!stack.length) {
        stack.push([price, index]);
        return;
    }
    while (stack.length) {
        const top = stack.pop();
        if (top[0] > price) {
            answer[top[1]] = index - top[1];
            continue;
        }
        stack.push(top);
        break;
    }
    stack.push([price, index]);
});

만일 stack이 비어있다면, price, index를 배열 형태로 stack에 넣어준다.
비어있지 않다면 stack.length가 0이상일때까지 반복문을 돌린다.

while 반복문 내부

stack.pop()메소드를 이용해 가장 위에 있는 원소를 꺼낸다.
해당 원소는 [value, index] 형태로 존재한다.
- 편의상 pop해서 얻은 값은 value, idx 로 부르겠다.

value의 값이 price보다 클 경우

value의 값이 price 보다 크면 answer[index]의 값을 업데이트 해준다.
index - idx 의 값으로 업데이트 해준다.
- 현재 index까지 값이 낮아지지 않았기에 index-idx로 업데이트해준다.
그 다음 stack의 가장 위에 있는 값도 확인해야하기에 바로 다음 반복문을 반복한다.
value의 값이 price 보다 작거나 stack의 길이가 0이 될때까지 반복한다.

value의 값이 price보다 같거나 작을 경우

pop해서 얻은 원소를 제거할 필요가 없으므로 다시 stack에 넣어준다.
value의 값이 price보다 크기때문에 더이상 검사할 필요가 없다.
따라서, 반복문을 중지시킨다.

반복문 중지 후

반복문을 나오면 현재 price와 index의 값을 stack에 배열 형태로 넣어준다.

answer 업데이트

stack.forEach((value) => {
    answer[value[1]] = prices.length - value[1] - 1;
});
return answer;

stack에 남아있는 원소들을 토대로 반복문을 돌린다.
prices의 길이에 1을 뺀 값에 idx값을 뺀 값을 answer[idx] 에 업데이트 시킨다.
현재 stack에 남아있는 값들은 끝까지 떨어지지 않는 값이므로 끝까지 존재했을 때 값을 answer에 업데이트시킨다.
반복문이 종료되면 answer값을 최종적으로 반환한다.

재귀로 풀기 - 효율성 에러

처음 문제를 풀때 while문이 아닌 재귀로 풀었었다.

하지만, 재귀로 풀경우 런타임에러가 발생했다.

정확한 원인은 더 알아봐야겠지만, 아마 stackoverflow가 발생하는게 아닐까 싶다.

const checkTop = (price, index) => {
    if (!stack.length) return;
    const top = stack.pop();
    if (top[0] > price) {
        answer[top[1]] = index - top[1];
        checkTop(price, index);
    } else {
        stack.push(top);
    }
    stack.push([price, index]);
};
prices.forEach((price, index) => {
    if (!stack.length) {
        stack.push([price, index]);
        return;
    }
    checkTop(price, index)
});

로직은 위의 로직과 동일하다.
단, 반복문이 아닌 재귀로 풀었다는 차이점만 존재한다.

👩‍💻 코드

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

    const checkTop = (price, index) => {
      if (!stack.length) return;
      const top = stack.pop();
      if (top[0] > price) {
        answer[top[1]] = index - top[1];
        checkTop(price, index);
      } else {
        stack.push(top);
      }
      stack.push([price, index]);
    };
    prices.forEach((price, index) => {
      if (!stack.length) {
        stack.push([price, index]);
        return;
      }
      // checkTop(price, index)
      while (stack.length) {
        const top = stack.pop();
        if (top[0] > price) {
          answer[top[1]] = index - top[1];
          continue;
        }
        stack.push(top);
        break;
      }
      stack.push([price, index]);
    });
    stack.forEach((value) => {
      answer[value[1]] = prices.length - value[1] - 1;
    });
    return answer;
  }

YUN SEO