문제 설명
정수로 이루어진 배열 numbers가 주어진다. 배열 내에서 각 원소들 보다 뒤에 있는 숫자 중에서 큰 숫자를 뒤에 있는 큰 수라고 한다. 각 요소들을 뒤에 있는 큰 수로 변환해서 출력하는데, 만약 배열 내에서 각 요소들 보다 뒤에 있는 숫자들 중에 큰 수가 없는 경우에는 -1을 담아서 출력한다.
문제 풀이
맨 처음 떠올린 문제 풀이 방법은 직관적으로 이중 for문을 돌리는 방법이었지만, 결과적으로 시간 초과가 발생했다. 아무리 생각해도 for문을 한번만 돌리는 방법이 생각나지 않아 질문하기를 통해 정답 코드를 확인했다.
스택을 이용한 풀이방법인데 원리는 간단하지만 이 설계 방법을 떠올리기가 매우 어려웠다.
풀이 방법을 설명하기 전에 answer, stack의 의미를 알아야 한다.
answer 배열은 말 그대로 최종적으로 출력할 배열이다. 각 요소들의 뒤에 있는 큰 수로 변환하고 큰 수가 없을 경우에는 -1로 변환하여 출력할 것이다. numbers 배열을 순회하면서 순차적으로 뒤에 있는 큰 수를 찾을 예정이기 때문에 numbers 배열의 길이만큼 -1로 초기화 해준다.
stack 은 numbers 배열을 순회하면서 아직 뒤에 있는 큰 수를 찾지 못한 answer 배열의 인덱스를 담을 것이다. 그리고 매번 numbers 배열을 순회할 때 마다 가장 최근 스택에 담긴 값(=가장 최근에 뒤에 있는 큰 수를 찾지 못한 answer 배열의 인덱스)의 numbers 배열 내의 값과 바로 뒤에 있는 numbers 배열의 값과 비교한다. 만약 바로 뒤에 있는 값이 큰 경우에는 뒤에 있는 큰 수를 찾은 것이기 때문에 stack에서 제거하고 answer 배열의 값을 업데이트 한다. 그리고 stack 안에 값들에 대해 동일한 작업을 수행하면서 answer 배열을 업데이트 한다.
function solution(numbers) {
const answer = Array(numbers.length).fill(-1);
const stack = [];
for (let i = 0; i < numbers.length; i++) {
while (numbers[stack.at(-1)] < numbers[i]) {
answer[stack.pop()] = numbers[i];
}
stack.push(i);
}
return answer;
}numbers - [2, 3, 3 ,5] / result - [3, 5, 5, -1]
이제 입출력 예시와 함께 전체 코드를 살펴보자. answer 배열을 numbers 배열의 길이만큼 값을 -1로 초기화 한다. answer 배열은 [-1, -1, -1, -1] 이렇게 초기화 됐다. 그리고 최초의 stack은 빈 배열 [] 이다. for문을 순회한다.
i = 0 일 때 numbers[undefined] < numbers[0] 이기 때문에 while문을 실행하지 않고 stack에 0을 push 한다. 즉, 뒤에 있는 큰 수를 찾지 못한 요소를 stack에 추가했다. 현재까지 해결하지 못한 요쇼는 stack에 담겨있는 요소 [0]이다.
i = 1 일 때 numbers[0] < numbers[1] 에서 numbers[1]의 값은 3이고 numbers[0]은 2이기 때문에 while문이 실행된다. 뒤에 있는 큰 수를 찾았다! 현재까지 해결하지 못한 가장 최근의 요소가 뒤에 있는 큰 수를 찾았기 때문에 answer[0]은 = numbers[1]이 된다. 이렇게 됐을 때 stack의 요소는 pop이 되어 빈 배열이 된다. 그리고 answer 배열에서 0번 째 요소는 뒤에 있는 큰 수를 찾아 [3, -1, -1, -1]이 된다. 그리고 stack에 1을 push 한다. numbers 배열에서 1번 요소는 아직 뒤에 있는 큰 수를 찾지 못했다는 의미이다.
i = 2 일 때 numbers[1] < numbers[2] 에서 numbers[1]과 numbers[2]는 3으로 서로 같기 때문에 while문을 실행하지 않고 stack에 2를 push 한다. stack은 [1, 2]가 담겨있어 numbers 배열에서 1번 2번 요소는 아직 뒤에 있는 큰 수를 찾지 못했다.
i = 3 일 때 numbers[2] < numbers[3] 에서 numbers[2]는 3이고 numbers[3]은 5이기 때문에 2번 요소는 뒤에 있는 큰 수를 찾았다. stack에서 pop을 해주고 해당 자리의 answer[2] 값을 numbers[3]으로 업데이트 해준다. 그리고 마찬가지로 numbers[1]도 3으로 numbers[3]의 값인 5보다 작기 때문에 뒤에 있는 큰 수를 찾았다. answer[1]을 numbers[3]으로 업데이트 해준다. 그리고 stack에 i를 push 한다. i = 3일 때는 마지막 요소이기 때문에 뒤에 있는 큰 수를 찾을 수 없어 이대로 for문을 종료한다. answer[3]의 값은 -1로 출력이 될 것이다.
이러한 과정을 거쳐서 [3, 5, 5, -1]이 출력된다.
정답 코드를 보고도 제대로 이해가 되지 않아 하나씩 값을 넣어봤더니 그래도 이해가 됐다. 간단한 코드처럼 보이지만 이런 설계를 할 수 있다는게 정말 대단하다...
출처: https://school.programmers.co.kr/learn/courses/30/lessons/154539
