출처: https://school.programmers.co.kr/learn/courses/30/lessons/154539
class Solution {
public int[] solution(int[] numbers) {
int[] answer = {};
// 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수
// 뒷큰수가 없으면 -1 2라고 쳐도 그 다음 인덱스에 자기 보다 큰 수 없으면 -1이다.
int 인덱스 = 0;
for(numbers수 만큼 돈다.){
if(그 다음 인덱스에 뒷큰수가 있는지?){
answer[인덱스] = 있으면 뒷큰수 저장;
인덱스++;
} else {
answer[인덱스] = -1; // 없으면 -1저장.
인덱스++;
}
}
return answer;
}}
그리고 약 30분정도 고민해서 만든 코드인데 어떻게 뒷큰수라는 표현을 코드로 자겅해야할지 모르겠다.
import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
int[] answer = new int[numbers.length];
// 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수
// 뒷큰수가 없으면 -1 2라고 쳐도 그 뒤 인덱스에 자기 보다 큰 수 없으면 -1이다.
for(int i = 0; i < numbers.length; i++){
for(int j = i + 1; j < numbers.length; j++){
if(numbers[j] > numbers[i]){// 그 뒤 인덱스에 뒷큰수가 있는지?
Math.min(numbers[j - 1], numbers[j]);
answer[i] = numbers[j];// 넣긴 넣되 최소한의 큰값이니
} else {
answer[i] = -1; // 없으면 -1저장.
}
}
}
return answer;
}}
위 코드의 문제점은
뒷큰수는 "가장 가까운" 수만 찾으면 되는데, for j 루프가 끝까지 돈 후에 대입해서 마지막 값이 들어가거나 -1로 덮일 수 있음.
Math.min()의 결과를 변수에 저장하지 않고 무시하고 있음.
else로 인해 큰 값이 나왔어도 다음 반복에서 -1로 덮어씌워짐.
그래서 이렇게 고쳐야 한다. 기본값으로 answer[i]배열에 -1저장.
그리고 넣긴 넣되 가장 가까운수만 넣어야하니
한번 answer[i]배열에 한번 저장하고 break; 해야한다.
다음은 수정된 코드문이다.
import java.util.*;
class Solution {
public int[] solution(int[] numbers) {
int[] answer = new int[numbers.length];
// 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수
// 뒷큰수가 없으면 -1 2라고 쳐도 그 뒤 인덱스에 자기 보다 큰 수 없으면 -1이다.
for(int i = 0; i < numbers.length; i++){
answer[i] = -1;
for(int j = i + 1; j < numbers.length; j++){
if(numbers[j] > numbers[i]){// 그 뒤 인덱스에 뒷큰수가 있는지?
answer[i] = numbers[j];// 넣긴 넣되 최소한의 큰값이니
break; // 더 이상 볼 필요 없음
}
}
}
return answer;
}}
이번에는 시간초과 에러가 뜬다.
시간복잡도를 개선할 아이디어가 필요하다.
import java.util.*;
class Solution { // 스택을 사용해서 풀어야하는 문제
public int[] solution(int[] numbers) {
int[] answer = new int[numbers.length];
Stack stack = new Stack<>();
stack.push(0); // 첫번째 인덱스 값
for(int i=1; i<numbers.length; i++) {
while(!stack.empty() && numbers[stack.peek()] < numbers[i]) {
answer[stack.pop()] = numbers[i];
}
stack.push(i); // 다음 인덱스 값을 넣어줌
}
// stack에 남은 인덱스 값들 = -1
while(!stack.empty()) {
answer[stack.pop()] = -1;
}
return answer;
}}
왜 하필 스택인가?
“최근의 값부터 비교하면서 조건 안 맞는 건 버리고, 조건 맞는 걸 기억해두자”
stack.push(i) "내 차례 기다릴게!" 하면서 인덱스 저장
numbers[stack.peek()] < numbers[i] "어, 기다리던 사람보다 내가 더 크네? 나를 뒷큰수로 넣자"
stack.pop() 뒷큰수 찾았으니 이제 제거
마지막 while문 끝까지 못 찾은 애들은 -1 처리
answer[stack.pop()] = -1; 의미
“스택에 남아 있는 인덱스는 끝까지 자기보다 큰 수를 못 만났구나 → -1 넣자!”
stack.push(x) 스택에 값 x 추가
stack.pop() 스택 맨 위 값 꺼내고 제거
stack.peek() 스택 맨 위 값 확인 (제거 X)
stack.isEmpty() or stack.empty() 비었는지 확인 (true/false)
