99클럽 코테 스터디 1일차 TIL + Programmers 뒤에서 큰 수 문제 풀이 (java)

1. 문제 링크

문제 링크

2. 접근 방식

백준에서 풀었던 오른쪽에서 큰 수와 같은 문제인데, 문제를 푸는 아이디어가 생각이 안나서, 저번에 풀었던 것 좀 봤다.
해당 문제는 Stack 자료구조를 이용하여 풀어야 한다.

나는 먼저 Node라는 Class를 만들었다. Node의 구조는 다음과 같다.

class Node {
    int i; // 원래 index 
    int v; // 값 

    public Node (int i, int v){
        this.i = i;
        this.v = v; 
    }
}

해당 Node를 자료형으로 가진 Stack을 만든다. 그리고 답을 저장하는 배열ans을 하나 더 만든다.
배열은 index = 원래 값의 위치, value = 해당 index 값의 뒷큰수가 무엇인지 저장 한다.

Node Stack의 규칙은 다음과 같다.

1. 입력으로 주어진 배열을 순회한다.
2. Stack이 비어있으면 현재 조회 중인 원소의 값을 저장한다.
3. Stack이 비어있지 않다면, 현재 조회 중인 값과 Stack.top을 비교한다.
   (1) 만약 Top이 더 크면, Stack에 현재 조회 중인 수를 저장하고 넘어간다.
   (2) 만약 반대로 현재 조회 중인 수가 더 크면 해당 수가 Top의 뒷큰수 이므로, ans의 Top 자리에 조회 중인 수를 뒷큰수로 저장한다. 그 후 Stack의 Top을 POP하고 다음 수에 대하여 3번 과정을 반복한다.
4. ANS가 채워졌을 것이다. 근데 ans의 값이 갱신되지 않은 녀석은 뒷큰수가 없다는 소리이므로 -1을 출력한다.

3. 코드 분석

class Solution {
    public int[] solution(int[] numbers) {
        // 원래의 인덱스와 값을 가진 stack
        Node [] stack = new Node [numbers.length];
        int top = -1; 
        // i = 원래 number 배열의 인덱스, value = numer[i]의 뒷큰수
        int [] NGE = new int [numbers.length]; 
        // 값 초기화
        for(int i = 0; i < numbers.length; i++){
            NGE[i] = -1;
        }

        for(int i = 0; i < numbers.length; i ++){
            Node now = new Node(i ,numbers[i]);
            if(top == -1){
                stack[++top] = now;
            }else {
                while(top > -1 && stack[top].v < now.v){
                    NGE[stack[top--].i] = now.v;
                }
                stack[++top] = now;
            }
        }
        return NGE;
    }
}

class Node {
    int i;   // index
    int v;   // 값

    public Node(int i, int v){
        this.i = i;
        this.v = v;
    }
}