[구현] 프로그래머스 '뒤에 있는 큰 수 찾기' - js

1. 문제

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

프로그래머스

2. 코드

이 문제를 푸는 방법에 2중 for문과 filter밖에 생각나지 않았다.. 둘 다 예상했던 대로 시간 초과 ㅠㅠ

n의 값이 워낙 커서 시간을 최대한 적게 쓰는 풀이가 필요했다.

function solution(numbers) {
    let answer = [];
    let newNumbers = numbers.map((el,idx) => [el,idx]);
    
    for(let i=0;i<numbers.length-1;i++){
        let cur = -1;
        let find = newNumbers.filter((el) => el[0] > numbers[i] && el[1] > i);
        if(find.length) cur = find[0][0];
        
        answer.push(cur);
    }
    answer.push(-1);
    
    return answer;
}

정답)

정답은 스택을 활용하는 것이였다. 머리 속에 살짝 스쳐만 지나간 스택..

function solution(numbers) {
  // 먼저 numbers의 길이 만큼 -1을 채운 배열을 만들어준다.
  const answer = new Array(numbers.length).fill(-1);
  // 인덱스를 넣을 배열
  const stack = [];

  for (let i = 0; i < numbers.length; i++) {
    // 스택에 인덱스가 존재하고, 해당 인덱스에 해당하는 값이 numbers[i] 보다 작을 경우 
    // numbers[i]가 해당 인덱스에 해당하는 값의 뒤 큰 수가 된다.
    while (stack.length && numbers[stack[stack.length - 1]] < numbers[i]) {
      // 그러므로, answer의 인덱스 위치에 현재 들어온 수를 넣어준다(뒤 큰 수).
      // while 문을 통해 그 전 인덱스에 해당하는 값들의 뒤 큰 수 여부도 판별된다.
      answer[stack.pop()] = numbers[i];
    }

    // 현재 가리키고 있는 인덱스를 넣어준다.(numbers[i]의 뒷 큰 수도 구해야 하므로)
    stack.push(i);
  }

  // 마지막은 인덱스의 뒤 큰 수는 for문의 종료로 확인할 수 없으므로 미리 세팅한 -1 그대로 남는다.
  return answer;
}

이중 for문과 스택 사용 방법에 대해 간단히 정리된 글이 있다!

https://school.programmers.co.kr/questions/47035

프로그래머스

 

복기

6/9