[JS] 2Level / 연습문제 / 연속 부분 수열 합의 개수

문제 설명

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

프로그래머스

문제 풀이 방법

이번에 다시 풀어본 문제는 시간 복잡도 최적화가 중요한 문제이다.

 

const solution = (numbers) => {
    let answer = new Array(numbers.length).fill(-1);
    
    for(let i = 0; i < numbers.length; i++){
        for(let j = i + 1; j < numbers.length; j++){
            if(numbers[j] > numbers[i]){
                answer[i] = numbers[j];
                break;
            }
        }
    }
    return answer;
}

위의 코드는 기존에 작성한 코드로써 테스트에서 거의 다 통과가 되었지만 4개의 케이스에서 시간초과가 발생했다. 계산 해보니 인수로 받는 numbers의 최대 길이는 1,000,000 이며 이중 반복문을 이용하면 시간 초과를 의심해봐야한다....

 

이 문제는 스택 자료구조를 이용해 numbers의 요소의 인덱스를 담아 스택의 마지막 인덱스를 순서대로 저장해 다음 순회의 요소와 스택에 담긴 인덱스에 해당하는 요소를 비교해 요소가 더 크다면 스택에서 pop메서드를 이용해 뽑아주고 답을 구한다.

 

정답 코드

const solution = (numbers) => {
  let answer = Array.from({ length: numbers.length }, () => -1);
  let stack = [];

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