오늘도 코트카타 TIL~ 다 즐찾 되어있던 문제다.
나에게 즐찾이란? 한 번에 풀지 못해서 나중에 또 풀어야집! 하고 찜해놨던 문제
역시나 다시 풀었더니 못풀었다ㅋㅋ

뒤에 있는 큰 수 찾기

링크텍스트

문제

풀이 방법 및 시행 착오

1. 이중 for문을 쓰면 효율성이 안좋을 것 같지만 처음 풀었을 때는 달리 방법이 생각나지 않았음
2. 앞 숫자보다 더 큰 뒷 숫자를 만났을 때 바로 break 해주면... 될 줄 알았음

오답코드

import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i=0; i<numbers.length; i++) {
            if(numbers[i] == 9) {
                answer[i] = -1;
            }
            for(int j=i+1; j<numbers.length; j++) {
                if(numbers[i] < numbers[j]) {
                    answer[i] = numbers[j];
                    break;
                }
            }
            //answer이 비어있다면 더 큰 숫자가 없다는 뜻 = -1
            if(answer[i] == 0) {
                answer[i] = -1;
            }
        }
        return answer;
    }
}

결과

테스트 코드는 통과하였지만 시간 초과!
아무래도 numbers의 길이가 백만이여서 그런가 보다...

다른 방법 도전!!!

스택 사용

했지만 실패한 코드

오답코드

//이중 for문은 효율성 초과
//스택 사용
import java.util.*;
class Solution {
    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        
        for(int i=0; i<numbers.length-1; i++) {
            
            Stack<Integer> stack = new Stack<>();
            
            if(numbers[i]<numbers[i+1]) {
                answer[i] = numbers[i+1];
            }
            else {
                int idx = i+1;
                while(numbers[i]>numbers[idx]) {
                    stack.push(numbers[idx]);
                    idx++;
                }
                answer[i] = numbers[idx];
            }
            
        }
        
        //비어있다면 -1
        for(int j=0; j<numbers.length; j++) {
            if(answer[j] == 0) {
                answer[j] = -1;
            }
        }
        
        return answer;
    }
}

결과

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
	at Solution.solution(Unknown Source)
	at SolutionTest.lambda$main$0(Unknown Source)
	at SolutionTest$SolutionRunner.run(Unknown Source)
	at SolutionTest.main(Unknown Source)

막연하게 죽죽 썼더니 오류 남

틀린 이유(GPT야 고마워) -> while(numbers[i] > numbers[idx])에서 idx++를 계속 증가시키는데, 만약 끝까지 큰 수가 없다면 ArrayIndexOutOfBoundsException이 발생할 수 있습니다.

사실 이 코드는 stack을 쓴 의미가 없는 그런 말도 안되는 코드...!!!!

정답 코드

//이중 for문은 시간 초과
//stack에 인덱스 넣기
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++) {
            while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
                answer[stack.pop()] = numbers[i];
            }
            stack.push(i);
        }
        
        //빈 곳에 -1 넣어주기
        for(int j=0; j<numbers.length; j++) {
            if(answer[j] == 0) {
                answer[j] = -1;
            }
        }
        return answer;
    }
}

stack에 인덱스를 넣는다

1. i=0일때 stack은 비어있으므로 0을 stack에 넣어준다.

2. while문에서 numbers[stack.peek(=인덱스)]과 numbers[i]의 값을 비교해준다.

3. while문의 조건을 충족하면 stack.peek()을 answer인덱스로 설정하여 큰 값(numbers[i])를 넣어준다. 이때, stack.peek의 값은 비교가 끝났으므로 stack.pop()을 해준다.

4. 빈 곳은 뒷 큰수가 없다는 뜻이므로 -1

쉽게 말해보자면
i -> 지금 비교해 볼 뒷 큰수
stack -> 뒷 큰수와 비교해 볼 앞의 수들

---

이것두 어렵고~ 저것도 어렵고~
stack 쓰는 건 알았지만 인덱스를 넣어야 하는 건.... 또 까먹은...
제출내역 보니 10개던데.. 못해도 4번은 풀었을텐데 또 까먹은게 신기하다.
이렇게 자세히 정리했으니 이젠 안까먹겠지!
금붕어 아니잖아....ㅜ