문제 출처
https://school.programmers.co.kr/learn/courses/30/lessons/154539
기존 풀이
function solution(numbers) {
const answer = [];
for (let i = 0; i < numbers.length - 1; i++) {
let j = i + 1;
while (numbers[i] >= numbers[j]) {
j++;
}
if (j === numbers.length) {
answer.push(-1);
} else {
answer.push(numbers[j]);
}
}
answer.push(-1);
return answer;
}for문안에 while문을 써서 현재인덱스의 뒤에서 큰수를 찾는 경우 answer에 넣는다. 이때, 마지막 까지 가서 while문을 나온경우는 큰 수가 없다는 뜻이므로 -1을 대입한다.
역시 Lv2답게 바로 오답..
반복문안에 반복문을 썼으니 반복문을 한 번 쓰도록 코드를 개선해야 한다.
Stack같은 알고리즘을 쓰는 거 같은데 도저히 몰라서 구글링을 하였다.
정답 풀이
function solution(numbers) {
let answer = new Array(numbers.length).fill(-1);
let stack = [];
for (let i = 0; i < numbers.length; i++) {
while (stack && numbers[stack.at(-1)] < numbers[i]) {
answer[stack.pop()] = numbers[i];
}
stack.push(i);
}
return answer;
}예상한대로 스택을 쓰긴 썼는데.. 어렵다!
설명해보자면
값이 정해지지 않는 것을 고려해 요소가 모두 -1 인 값을 가진 result 생성
stack에는 아직 뒷 큰수를 찾지 못한 원소의 인덱스를 저장
- numbers를 한번씩 돌면서 아래과정 체크
- 만일 스택에 값이 있고, stack 맨 앞 값 < numbers[i] 라면 그 stack index는 numbers[i] 가 가장 가까운 값이라고 정함. 해당 인덱스를 pop하면서 result에 바꿔치기, 아닌경우 3번(이전의 수와 겹칠때)
- stack에 인덱스 i를 push
O(N)의 시간복잡도를 가진다.
추가
왜 O(N)의 시간복잡도를 가질까..? 솔직히 내가 원래 작성했던 풀이와 예상 시간복잡도가 크게 다르지 않을거라 생각했다. 도저히 모르겠어서 학교에서 알고리즘을 매우 잘하는 분 한테 개인적으로 카톡을 했는데 아~주 열심히 대답해주셨다.. 덕분에 알고리즘 공부방법도 알아갔다.
핵심은 역시 Stack에 있었다.
stack은 반복문을 돌때마다 원소를 오직 한 번만 넣고 뺀다. 왼쪽에서부터 뒤큰수를 찾게되면 즉시 스택에서 빼고 그 수를 다음 연산에서 사용하지 않는다.
하지만 원래의 풀이는 뒤큰수를 찾게된다해도 같은 수에 대해서 연산을 계~속하게 되므로 input이 늘어나면 늘어날수록 + 배열이 역순으로 되어있으면 시간복잡도가 차이가 많이가 나게 된다.
추가로 이 문제에서 스택 풀이를 어떻게 생각했는지 사고의 흐름을 정리해보자.
만약 input 배열이 [9, 1, 5, 3, 6, 2] 이라고 하자.
- 뒤 큰수는 말 그대로 자신보다 뒤에 큰 수가 오게 된다.
- 당연한 사실이지만 앞에서부터 수를 찾아갈 때 9보다 큰 값은 5보다 크다.
- 뒤 큰수는 처음으로 큰 수를 만나는 순간부터 정해진다. 만약 9 1 5 상황에서는 1의 뒤큰수는 5가 되고, 1은 더이상 사용하지 않아도 된다!
9 1 5 -> 9 5 -> 9 5 3 -> 9 5 3 6 -> 9 5 6 -> 9 6
이런식으로 오른쪽에서 넣고 뺀다는 성질을 이용해 스택을 떠올릴 수 있다.
사실 제일 중요한건 문제풀이를 볼때, 코드를 보고 문제풀이 방식을 이해하려 하지 말고, 반드시 글이나 그림과 같은 설명을 통해 문제풀이 방식을 먼저 이해해야 한다는 것이다.
