스택 자료구조 풀이#6

스택 문제 (프로그래머스 : 주식가격)

• 문제 설명
  초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.

• 제한사항
  prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.
  prices의 길이는 2 이상 100,000 이하입니다.

나의 풀이

• 반목문을 돌리고 , while문을 써서 하나의 요소를 기준으로 다른 요소들을 비교하자.
• 2개의 반복문이 사용됐고, 아래의 주석의 흐름에 따라서 문제를 풀이했습니다,

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

  let arrLength = prices.length;

  for (let i = 0; i < prices.length; i++) {
    // 마지막 요소는 다음 비교군이 없으므로 0으로 끝
    if (i === arrLength - 1) {
      answer.push(0);
    }
    // 마지막 요소가 아닌경우
    else {
      let h = i + 1;
      let count = 0;

      while (h > 0 && h < arrLength) {
        // 다음 요소와 비교해서 , 다음요소가 크거나 같을 경우 줄어들지 않음
        if (prices[i] <= prices[h]) {
          count++;
          if (h === arrLength - 1) {
            answer.push(count);
            break;
          }
          h++;
        } else {
          count++;
          answer.push(count);
          h = 0;
        }
      }
    }
  }

  return answer;
}

console.log(solution([1, 2, 3, 2, 3]));

---

GPT의 풀이 및 개선해야할 점

풀이방향

• prices 배열을 탐색하면서 현재 인덱스를 스택에 저장
• 스택의 최상단 요소가 현재 요소보다 큰 경우, 스택에서 해당 요소 제거 후 해당 요소의 결과값을 현재 인덱스와 스택에서 제거된 인덱스의 차이로 설정
• 모든 요소를 탐색한 후에도 스택에 남아있는 인덱스에 대해 남은 기간을 계산해서 answer 배열에 기록

=> O(n) 의 시간 복잡도를 가진다.

But, 나의 풀이는 O(n2)의 시간복잡도를 가지기에 효율적이지는 못하다.

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

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

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

    return answer;
}

---

배울점

• 이번 코테는 문제없이 풀기는 했다. 그러나, 스택 자료구조라는 카테고리를 알고 들어갔는데, 풀고나니 자료구조 활용을 한 것 같지 않는데?라는 생각이 들었고, GPT에서 답을 얻은 결과 역시나 최선의 방법은 아니였다.
• 이번 풀이를 보면서 , 어떡식으로 풀이를하고 생각을 해야 좋은지, 시간 복잡도 측면에서 좋은지도 좀 더 생각하고 공부해봐야겠다.