[백준] 17298 오큰수 JAVA

1. 문제 설명

문제 링크

2. 접근 방식

0. 사전 세팅

• Node Class : 멤버 변수로 index와 value를 가지고 있다. index는 입력에서 해당 값이 나온 순서를 저장하고, value는 실제

  값을 저장한다.

• NGE 배열 : index에 해당하는 입력 값의 오큰수가 무엇인지 저장한다.

• top : stack을 배열로 구현하였기 때문에 top이 어디인지 알려줄 변수로 사용했다.

1. 원리

• stack이 비어있으면 현재 조회 중인 입력값을 넣는다.

• stack이 비어있지 않은 경우 stack.top과 현재 조회 중인 입력값(A)를 비교한다.

  • stack.top < A 인 경우
    stack.top의 오큰수는 A이므로 NGE 배열의 top의 index에 A를 저장한다.
    stack.top의 오큰수는 정해졌음으로 pop하고, 그 다음 top과 A를 또 비교한다.

  • stack.top >= A인 경우
    stack.top의 오큰수는 아직 나오지 않았다. 따라서 A를 stack에 push한다.

• NGE 배열을 출력하면 각 위치별 오큰수를 구할 수 있다.

  • 이때 값이 0인 부분은 입력 전체에서 오큰수가 없는 수이다. 해당 값은 -1로 변환하여 출력한다.

3. 코드 분석

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        Node [] stack = new Node [N];
        int [] NGE = new int [N];
        int top = -1;

        StringTokenizer st = new StringTokenizer(br.readLine());
        stack[++top] = new Node(0, Integer.parseInt(st.nextToken()));

        for (int i = 1; i < N; i++) {
            Node now = new Node(i, Integer.parseInt(st.nextToken()));

            while (top != -1 && stack[top].v < now.v){
                NGE[stack[top].i] = now.v;
                stack[top--] = null;
            }

            if(top == -1 || stack[top].v >= now.v){
                stack[++top] = now;
            }
        }

        for (int value : NGE){
            sb.append(value == 0? -1 : value).append(" ");
        }

        System.out.println(sb);

    }
}

class Node {
    int i;
    int v;

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

4. 성장하기

나는 해당 문제를 풀기 위해, 클래스를 사용하였다. 가독성 면에서는 좋지만, 속도 면에서 조금 느려질 수 있다. 그래서 책에 있는 풀이를 봤더니 다음과 같이 문제를 풀었다.

1. stack에는 index만 push, pop 하고, value를 다른 배열(value)에 따로 저장해서, 이것을 통해 비교한다.
   예를 들어, value[stack[top]] < value[i] (stack의 최상단에 있는 값과 현재 조회 중인 값을 비교)
2. 내가 클래스를 만들어서 index와 value를 묶어 관리하던 것을 index용 stack과 value용 배열로 나누어서 관리하는 것이다.

이렇게 푸니까, 조금이지만 속도가 줄어들었다.

5. 다른 풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int [] value = new int[N];      // index에 해당하는 value 저장
        int [] stack = new int[N];      // index 만 저장
        int [] nge = new int[N];        // index 당 자신의 오큰수 저장
        int top = -1;

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            value[i] = Integer.parseInt(st.nextToken());
        }
        stack[++top] = 0;

        for (int i = 1; i < N; i++) {
            // 현재 조회 중인 값보다 stack의 top 값이 작은 경우
            while(top != -1 && value[stack[top]] < value[i]){
                nge[stack[top--]] = value[i];
            }

            if(top == -1 || value[stack[top]] >= value[i]){
                stack[++top] = i;
            }
        }

        for (int now : nge){
            sb.append(now == 0? -1 : now).append(" ");
        }

        System.out.println(sb);
    }
}