[백준] 17298번 - 오큰수 (Java)(○)

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

<풀이 #1>

1. 수열이 A1 ~ An 만큼 있다. 각 수열의 오큰수를 구해야 한다.

2. 오큰수란? Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수이다. 없으면 -1이다.

3. 오큰수 구하기 로직

  - Ai가 가장 오른쪽 수이면 -1이다.

  - Ai 보다 큰 수가 없으면 -1이다.

  - Ai의 오른쪽 수를 순차적으로 비교해서 더 크면 스택에 push 한다.

  - 스택이 빌 때까지 pop을 하고 제일 마지막 수를 출력한다.

  - 비교를 다 했는데 스택이 비었으면 -1을 출력한다.

 

<구현 #1>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    static int N;
    static int A[];

	void Solve() {
        Stack <Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<N; i++) {
            if (i == N-1) {
                sb.append(-1+" ");
                break;
            }
            for (int j=i+1; j<N; j++) {
                if (A[j] > A[i]) {
                    stack.push(A[j]);
                }
            }
            if (stack.isEmpty()) {
                sb.append(-1+" ");
            } else {
                int num = 0;
                while(!stack.isEmpty()) {
                    num = stack.pop();
                }
                sb.append(num+" ");
            }
        }
        System.out.println(sb.toString());
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}

 

<Hint>

1. 입력값의 범위가 N이 1 ~ 1,000,000 이라서 O(N^2) 알고리즘을 사용하면 1초의 시간 제한을 통과하지 못한다.

따라서 O(N) 알고리즘을 사용해야 한다.

 

2. 스택에 있는 수열의 정의

  - 오큰수를 구하지 못한 수들만 스택에 남는다.

  - 스택에는 배열의 인덱스를 넣는다. 왜냐하면 오큰수가 있을 수도 있고 아닐 수도 있는데 답은 순차적으로 출력해야 한다. 스택에 오큰수를 못구한 수들을 나중에 일괄처리해야 하기 때문에 인덱스가 아닌 값을 저장하면 순서를 구분할 수가 없다.

3. 오큰수 구하는 로직

  - 스택에 첫 인덱스를 push한다.

  - 스택의 값과 A[i]를 비교해서 < A[i]이면 오큰수이므로 A[i]를 result[pop()] 에 저장한다.

  - A[n]까지 반복한다.

4. 스택에 남아있는 오큰수를 구하지 못한 수들은 result[pop()] = -1로 업데이트 해준다.

 

※ 스택을 사용한 문제풀이 팁 1. 입력범위가 1 ~ 1,000,000인 경우 자료구조(stack)을 사용하는 경우가 많은 것 같다.    - 10억 정도로 아예 클 경우는 이분탐색이 많다.   - 백만 정도면 O(N^2) 알고리즘을 사용하면 백프로 타임아웃이 발생한다. 2. 스택에 남기는 수의 역할, push의 역할, pop의 역할을 정의해야 한다.   - 스택에 넣는 수 : 다음 A[i]와 비교해서 오큰수를 찾기 위해서   - 마지막에 스택에 남은 수들 : 오큰수를 못찾은 수들   - push() : 다음 인덱스와 비교하기 위해 추가   - pop() : 정답 배열에 값을 추가

 

 

<구현>

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    static int N;
    static int A[];
    static int result[];

	void Solve() {
        Stack <Integer> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        result = new int[N];
        // 스택에는 오큰수를 못구한 수들이 존재한다.
        stack.push(0);
        for (int i=1; i<N; i++) {
            // 스택에 저장된 수들의 오큰수를 구하는 로직
            while (!stack.isEmpty() && A[stack.peek()] < A[i]) {
                int idx = stack.peek();
                // A[i]가 오큰수라면 스택에서 idx를 제거한다
                if (A[idx] < A[i]) {
                    stack.pop();
                    result[idx] = A[i];
                }
            }
            // i의 오큰수를 구하기 위해 스택에 push 되어야 한다
             stack.push(i);
        }
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            result[idx] = -1;
        }

        for (int x : result) {
            sb.append(x+" ");
        }
        System.out.println(sb.toString());
	}

    void inputData() throws Exception {
        InputStreamReader reader = new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(reader);
        N = Integer.parseInt(br.readLine());
        A = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
    }

    public static void main(String[] args) throws Exception {
        Main m = new Main();
        m.inputData(); // 입력 받는 부분
        m.Solve();// 여기서부터 작성
    }
}