프로그래머스 뒤에 있는 큰 수 찾기 JavaScript
2023년 1월 27일
문제 풀이
정수로 이루어진 배열에서 배열의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 찾는 문제다. 입력 배열의 최대 크기가 1,000,000이기에 완전 탐색으로는 풀 수 없다. 따라서 stack을 이용해 풀었다.Numbers의 맨 뒤부터 탐색하며 현재 수의 오른쪽에 위치한 수들과 비교하기 위해 배열 rightNumbers를 이용한다.
맨 뒤의 수는 오른쪽에 숫자가 없기에 -1을 answer에 push 하고 rightNumbers에 push 한다. 그 뒤부터는 rightNumbers의 맨 뒤 숫자랑 현재 숫자를 비교하여 현재 숫자와 같거나 작을 경우 rightNumbers를 pop 하는 동작을 현재 숫자가 더 작을 때까지 반복한다. 현재 숫자의 탐색이 끝나면 rightNumbers에 push 한다.
뒤의 인덱스부터 탐색했기에 마지막에 reverse 한 후 리턴한다.
solution.js
function solution(numbers) {
let answer = [];
const Numbers = [...numbers];
const rightNumbers = [];
while (Numbers.length > 0) {
const number = Numbers.pop();
let bigNumber = -1;
let idx = rightNumbers.length - 1;
while (rightNumbers.length > 0) {
const rightN = rightNumbers[idx];
if (rightN <= number) {
idx--;
rightNumbers.pop();
}
else {
bigNumber = rightN;
break;
}
}
rightNumbers.push(number);
bigNumber === undefined ? answer.push(-1) : answer.push(bigNumber);
}
answer.reverse();
return answer;
}