문제 설명
정수로 이루어진 배열 numbers가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.정수 배열 numbers가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.
제한사항
•
4 ≤ numbers의 길이 ≤ 1,000,000
◦
1 ≤ numbers[i] ≤ 1,000,000
입출력 예
numbers | result |
[2, 3, 3, 5] | [3, 5, 5, -1] |
[9, 1, 5, 3, 6, 2] | [-1, 5, 6, 6, -1, -1] |
입출력 예 설명
입출력 예 #12의 뒷 큰수는 3입니다. 첫 번째 3의 뒷 큰수는 5입니다. 두 번째 3 또한 마찬가지입니다. 5는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [3, 5, 5, -1]이 됩니다.
입출력 예 #29는 뒷 큰수가 없으므로 -1입니다. 1의 뒷 큰수는 5이며, 5와 3의 뒷 큰수는 6입니다. 6과 2는 뒷 큰수가 없으므로 -1입니다. 위 수들을 차례대로 배열에 담으면 [-1, 5, 6, 6, -1, -1]이 됩니다.
나의 풀이
import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
int[] answer = new int[numbers.length];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < numbers.length; i++) {
int ri = numbers.length - 1 - i;
int num = numbers[ri];
while (!stack.empty() && num >= stack.peek()) {
stack.pop();
}
if (stack.empty()) {
answer[ri] = -1;
} else {
answer[ri] = stack.peek();
}
stack.push(num);
}
return answer;
}
}
Java
복사
Remark
•
•
풀이 아이디어
◦
배열 뒤부터 시작해서 숫자를 스택에 넣어가며 풀이함
◦
어떤 수의 입장에서는, ‘뒷 큰수’보다 더 뒤에(오른쪽에) 그보다 작거나 같은 수가 있는 것은 아무런 의미가 없음. 앞의 큰 수에 가려져 이후에 뒷 큰수가 될 가능성이 0이기 때문임
◦
따라서 왼쪽에서 오른쪽으로 집어넣는 스택이라고 그려볼 때, 새로운 수가 들어올 때 본인보다 작거나 같은 수를 모두 pop 시킨 후에 들어오도록 함
▪
들어가는 수 본인에 의해 무의미해진 숫자를 뽑아냄과 동시에 뒷 큰수를 찾는 과정
▪
최종적으로는 오른쪽으로 갈수록 큰 모양의 스택이어야 함
◦
본인보다 큰 수를 만나면 그 수를 answer 배열에 넣고, 모두 pop되어 스택이 빈 경우는 새로 들어온 수보다 큰 수가 없었다는 말이기 때문에 -1을 줌
•
다른 분 풀이
◦
같은 원리인데, 왼쪽으로 넣는 스택이고 값 대신 index를 사용하는 방식
import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
int[] answer = new int[numbers.length];
Arrays.fill(answer, -1);
Stack<Integer> s = new Stack<>();
s.push(0);
for(int i = 1; i < numbers.length; i++){
while(!s.isEmpty()){
int idx = s.pop();
if(numbers[i] > numbers[idx]){ // 뒤가 더 클때
answer[idx] = numbers[i];
} else { // 앞이 더 크거나 같을 때
s.push(idx);
break;
}
}
s.push(i);
}
return answer;
}
}
Java
복사
•
처음엔 아래처럼 중복 코드도 많고 비효율적으로 풀이를 했는데, 아쉽지만 일단 먼저 정답을 맞추고 그 다음 코드를 개선하는 쪽이 그래도 맞는 것 같음. 선 구현 → 후 최적화
import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
int[] answer = new int[numbers.length];
Stack<Integer> stack = new Stack<>();
loop:
for (int i = 0; i < numbers.length; i++) {
int ri = numbers.length - 1 - i;
int num = numbers[ri];
if (stack.empty()) {
answer[ri] = -1;
stack.push(num);
continue;
}
while (num >= stack.peek()) {
stack.pop();
if (stack.empty()) {
answer[ri] = -1;
stack.push(num);
continue loop;
}
}
answer[ri] = stack.peek();
stack.push(num);
}
return answer;
}
}
Java
복사
