뒤에 있는 큰 수 찾기 [자바]

 

🧫 문제 분석

✔️ 출처

뒤에 있는 큰 수 찾기 level 2

📖 문제

 

스택 구조를 써야될거같은 느낌이 든다. 

 

스택이 비어있다면 숫자를 넣는다. 

 

스택이 비어있지 않다면 

1. 스택의 TOP 원소와 현재 숫자를 비교해서 더 크다면 그 수가 뒷 큰 수 이다.

2. TOP원소를 꺼내서 numbers에 있었던 당시 인덱스를 answer 배열의 인덱스에서 뒷 큰 수를 넣어준다.

이를  1번이 false일 때까지 반복한다.

 

마지막으로 스택에 남은 뒷 큰 수가 없는 숫자들은 -1로 처리해준다.

 

---

🔅 문제 풀이 

import java.util.Stack;

class Solution {

    // 스택을 이용
    // idx를 함께 저장
    // 스택 top 원소 < 뒷수 -> 뒷 큰수 넣고, pop()

    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<int[]> stack = new Stack<>();

        for (int i = 0; i < numbers.length; i++) {
            if (stack.isEmpty()) {
                stack.push(new int[] {numbers[i], i});

            } else {
                while (!stack.isEmpty()) {
                    if (stack.peek()[0] < numbers[i]) {
                        int idx = stack.pop()[1];
                        answer[idx] = numbers[i];
                    } else {
                        break;
                    }
                }
                // 뒷 큰수를 다 처리했다면 현재 number를 스택에 저장
                stack.push(new int[] {numbers[i], i});
            }
        }

        // 뒷 큰수가 존재하지 않은 원소는 -1 처리 
        while (!stack.isEmpty()) {
            int idx = stack.pop()[1];
            answer[idx] = -1;
        }        


        return answer;
    }
}

 

 

🔅 리팩토링

import java.util.Stack;
import java.util.Arrays;

class Solution {

    public int[] solution(int[] numbers) {
        int[] answer = new int[numbers.length];
        Stack<Integer> stack = new Stack<>();
        
        Arrays.fill(answer, -1);
        
        for (int i = 0; i < numbers.length; i++) {
            while (!stack.isEmpty()) {
                int idx = stack.peek();
                
                if ( numbers[idx] < numbers[i]) {
                    answer[idx] = numbers[i];
                    stack.pop();
                    
                } else {
                   break;
                }
            }
            stack.push(i);
        }
        
        return answer;
    }
}

다른 분의 코드를 참고해서 했다.

기본 값을 -1로 해놓은 것과 while문을 먼저 두는 것도 되게 좋은 것 같다. 

배울점이 많다. 

 

 

❗ 오답노트 / 필요한 지식

1. 우선적으로 할 것은 일단 코드가 돌아가게 한다.