[JAVA]BOJ 17298, 오큰수

스택을 이렇게도 쓸 수 있구나 하고 깨달은 문제이다. 문제 자체는 간단해보이는데 시간제한내에 풀려면 스택을 꼭 써야한다. 그리고 출력시에도 주의가 필요하다.

 

풀기위해 필요한 필드는 입력받는 배열1, 결과값 저장하는 배열2, 빈 스택, 해서 총 3가지가 필요하다.

1. 배열1에 입력을 받는다.

2. 배열1의 마지막 값부터 스택값과 비교한다.

3-1. 스택이 비어있으면 -1을 배열2에 추가한다.

3-2. 스택 맨 위 값이 더 크면 오큰수이므로 peek()값을 배열2에 추가한다.

3-3. 스택 맨 위 값이 작거나 같으면, 스택 3-1, 3-2의 조건이 될때까지 pop()을 한다.

 

이렇게 설명하면 어려우니까 한 단계씩 풀어보자. 입력값 : 3 5 2 7 , 굵은 글씨가 스택이다.

-                                  -> 7
7 -> 스택이 비어있음 -> -1, 스택에 7 추가

                                                   2
7                                            -> 7
2 -> 스택맨위값(7)보다 작음 -> 7, 스택에 2 추가
 
2                                                                                                                    5
7                                         -> 7                                                                -> 7
5 -> 스택맨위값(2)보다 큼 -> 2꺼내기(pop) -> 스택맨위값(7)보다 작음 -> 7, 스택에 5 추가

                                                  3
5                                                5
7                                            -> 7
3 -> 스택맨위값(5)보다 작음 -> 5, 스택에 3추가

<끝>

 

 

이렇게 푸는게 가능한 이유

• 오큰수는 N[i]와 N[i+1]를 비교한다. N[i]가 N[i+1]보다 작으면 답은 N[i+1]이고,  N[i]가 N[i+1]보다 크면 N[i+1] 뒤의 값들을 보게된다.
• N[i+1] 뒤의 값들을 볼때, N[i+1]보다 작은 N[i+(2, 3...)]들은 볼 필요가 없다. 그래서 스택에서 지워지게된다. N[i+1]보다 큰 N[i+(2, 3...)]만 스택에 저장되고, N[i]와 비교하게 된다.
• X 5 2 1 7 을 예로 들면, X가 3일때 3 < 5(X < 5) 라서, 스택에 [5 2 1 7 이 있더라도 오큰수는 5가된다.
• X가 6일때 6 > 5(X > 5)라서, 5뒤의 숫자들을 보게된다. 그때 굳이 2, 1을 볼 필요가 없다. 2와 1은 5보다 작기 때문이다. 애초에 2와 1을 스택에 넣지 않아도 된다. 

설명하는데도 꼬여서 이해가 잘 될지 모르겠다.. 스택으로 푸는건 알겠는데 왜 이렇게 풀 수 있는거야? 무슨 원리야?? 라는 질문이 스스로 들어서 연구(?)해봤다. 어렵다 어려워~

 

 

그리고 출력시에 그냥 ans배열을 하나씩 sout으로 출력했더니 시간초과가 났다..ㅎ BufferWriter를 쓰려다가 귀찮아서 sout썼는데... 이번에는 BufferWriter말고 얼마전에 쓴 StringBuilder를 활용해서 출력했고 시간초과가 나지 않았다~~

---

아래는 전체 코드이다.

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

public class BOJ17298 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Integer> stack = new Stack<>();
        StringTokenizer st;
        int N, i;

        N = Integer.parseInt(br.readLine());
        int[] NGE = new int[N];
        int[] ans = new int[N];

        // 입력값 배열에 저장
        st = new StringTokenizer(br.readLine());
        for(i=0;i<N;i++){
            NGE[i] = Integer.parseInt(st.nextToken());
        }

        // 배열의 끝에서부터 오큰수 찾기
        for(i=N-1;i>=0;i--){
            while (!stack.isEmpty() && stack.peek() <= NGE[i]) // 현재 원소보다 크지않은 값 스택에서 제거
                stack.pop();

            if(stack.isEmpty()) // 스택이 비어있으면 오큰수는 -1
                ans[i] = -1;
            else if(stack.peek() > NGE[i]) // 스택값이 더 크면 오큰수
                ans[i] = stack.peek();

            stack.push(NGE[i]); // 한 턴이 끝났으니 값 추가
        }

        StringBuilder sb = new StringBuilder();
        for (i = 0; i < N; i++)
            sb.append(ans[i]).append(' ');
        System.out.println(sb);
    }
}