백준 17298 오큰수 자바

<문제>

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

17298번: 오큰수

 

<풀이>

해당 문제를 이중 for문으로 문제를 해결하려고 하면 N의 크기가 1,000,000이기 때문에 1,000,000 * 1,000,000 연산을 수행하는 경우가 생기기에 시간초과가 발생할 것이다.

그럼 이 문제를 어떻게 해결을 해야할까? 바로 stack을 이용해 문제를 해결하는 것이다.

결국 이 문제는 i번째 숫자보다 오른쪽에 위치한 숫자중에 i보다 큰 수들 중에서도 가장 왼쪽에 있는값을 구하는 것이다.

이렇게 생각했을때 Stack의 LIFO 특성을 이용해서 문제를 해결 할 수 있다.

배열을 돌면서 stack이 비었을경우 해당 인덱스를 스택에 넣는다. 만약 stack에 값이 존재하고 스택의 최상단의 인덱스 위치의 배열 값과 현재 위치의 값을 비교해서 만약 현재 위치의 값이 클경우 스택에서 꺼낸 인덱스 배열의 본인 숫자를 넣고 본인 인덱스는 다시 스택에 넣는다. 이러한 행위를 반복한 이후에 스택에 있는 값들(오큰수가 존재하지 않는 위치)을 다 꺼내서 해당 인덱스위치의 배열의 값을 -1로 변경하고 값을 출력하면 된다.

 

첫번째 예시같은 경우 위 풀이대로 문제를 진행하게되면 배열의 변화를 보여주자면

3 5 2 7 (입력 값)

5 5 2 7

5 5 7 7

5 7 7 7

5 7 7 -1

이런식으로 변하게 된다. 

 

두번째 예시같은 경우

9 5 4 8(입력값)

9 5 8 8

9 8 8 8

-1 8 8 -1

이런식으로 변하게 된다.

 

<코드>

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

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[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) { // 스택의 인덱스 위치의 배열값과 현재 배열값을 비교
                arr[stack.pop()] = arr[i];
                //System.out.println(Arrays.toString(arr));
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) { // 반복문이 끝났을때 스택에 있는 값은 오큰수가 없는 값들이므로 해당 인덱스 위치에 -1값을 저장
            arr[stack.pop()] = -1;
        }
        for(int i = 0; i < n; i++) {
            sb.append(arr[i]).append(" ");
        }
        System.out.println(sb);


    }
}

 

이문제에서는 StringBuilder를 쓰지 않고 출력을 하게 될경우 타임아웃이 걸리게 된다. 그러므로 StringBuilder를 꼭 사용해야 한다.