코딩테스트 연습 - 뒤에 있는 큰 수 찾기 | 프로그래머스 스쿨 (programmers.co.kr)
알고리즘 : 스택
처음에 아무 생각 없이 풀었더니 시간초과...
30분정도 풀어보다가 도저히 모르겠어서 정답을 참고해서 풀었다.
인덱스와 스택을 활용해서 푸는 방식이었는데 아직 시간복잡도를 이해하지 못한 것 같다.
처음에 n이 1,000,000인 것을 보고 n의 시간복잡도로 풀어야겠다! 까지는 되는데 실제 문제를 풀면 어려운것 같다.
핵심 알고리즘은 하기와 같다.
1. ans는 -1로 초기화 시켜준다.
2. for문을 돌면서 stack의 마지막 값과 현재의 값을 비교하고, 현재 값이 더 크다면 스택에서 pop해주면서 현재값으로 ans에 추가한다.
3. while문에 걸리지 않으면 stack에 그대로 넣어준다.
function solution(numbers) {
let ans = new Array(numbers.length).fill(-1);
let stack = [];
for (let i = 0; i < numbers.length; i++) {
let num = numbers[i];
while (stack.length && numbers[stack.at(-1)] < num) {
ans[stack.pop()] = num;
}
stack.push(i);
}
return ans;
}
'코딩테스트(알고리즘) > 프로그래머스' 카테고리의 다른 글
[프로그래머스] 택배 배달과 수거하기 (Javascript) (0) | 2023.02.10 |
---|---|
[프로그래머스] 숫자 변환하기 (Javascript) (0) | 2023.02.09 |
[프로그래머스] 무인도 여행 (Javascript) (0) | 2023.02.09 |
[프로그래머스] 호텔대실 (Javascript) (0) | 2023.02.09 |
[프로그래머스] 2 x n 타일링 (Javascript) (0) | 2023.02.07 |