Question
https://school.programmers.co.kr/learn/courses/30/lessons/154539
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
Algorithm
- 이전에 본 값들의 인덱스를 저장해두고, 더 큰 수가 나올 때까지 비교해야 하므로 스택을 사용한다.
- 배열을 왼쪽부터 오른쪽으로 순회하면서, 현재 숫자가 스택 top 인덱스의 값보다 크면 answer 값을 갱신한다.
- 아직 이 인덱스의 값보다 큰 수를 못 찾았은 경우, 뒤에서 더 큰 수를 만날 때까지 대기시키기 위해 스택에 보관한다.
- 배열 순회가 끝난 후, 스택에 남아 있는 인덱스들은 더 큰 수를 못 만난 것이므로 answer를 -1로 채운다.
Code
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
public int[] solution(int[] numbers) {
int[] answer = new int[numbers.length];
// 인덱스를 저장할 스택 (Deque 사용, LIFO 구조)
Deque<Integer> stack = new ArrayDeque<>();
// 배열을 순회하면서
for (int i = 0; i < numbers.length; i++) {
// 현재 숫자가 스택의 top에 해당하는 인덱스의 값보다 크다면
// 해당 인덱스에 대한 "뒤에 있는 큰 수"를 찾은 것
while (!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
// 스택에서 인덱스를 꺼내고
int index = stack.pop();
// 해당 위치에 현재 숫자를 저장
answer[index] = numbers[i];
}
// 현재 인덱스를 스택에 추가 (아직 뒤에 있는 큰 수를 못 찾은 상태)
stack.push(i);
}
// 스택에 남아있는 인덱스들은 "뒤에 있는 큰 수"가 없었던 것
while (!stack.isEmpty()) {
int index = stack.pop();
answer[index] = -1; // 뒤에 더 큰 수가 없으므로 -1 설정
}
return answer; // 결과 배열 반환
}
}
출처
https://hb-in99.tistory.com/59
프로그래머스 - 뒤에 있는 큰 수 찾기 <9점> - 자바 java Stack
문제가 level 2치고는 간단해 보였다. 구현 문제자나~~ 시간 복잡도만 고려하면 되겠다 싶었다. 일단 문제 그대로 읽으면서 구현해봤다. 뒤에 큰수를 찾으면 max에 저장해두고, 해당값을 answer[i]에
hb-in99.tistory.com
'Coding Test > [프로그래머스] Java' 카테고리의 다른 글
[프로그래머스 / Java] Lv.1 가장 가까운 같은 글자 (1) | 2025.06.14 |
---|---|
[프로그래머스 / Java] Lv.1 이상한 문자 만들기 (0) | 2025.06.13 |
[프로그래머스 / Java] Lv.2 할인 행사 (1) | 2025.06.11 |
[프로그래머스 / Java] Lv.2 예상 대진표 (1) | 2025.06.10 |
[프로그래머스 / Java] Lv.2 점프와 순간 이동 (1) | 2025.06.09 |