백준 17298 - 오큰수

문제

크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하려고 한다. Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오큰수는 -1이다.

예를 들어, A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1이다. A = [9, 5, 4, 8]인 경우에는 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

---

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다.

출력

총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력한다.

---

예제 입력 1

4
3 5 2 7

예제 출력 1

5 7 7 -1

예제 입력 2

4
9 5 4 8

예제 출력 2

-1 8 8 -1

---

풀이

public class Q17298_오큰수 {

    //최대 값만 찾아짐
//    public static void main(String[] args) throws IOException{
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        StringTokenizer st = new StringTokenizer(br.readLine());
//        int n = Integer.parseInt(st.nextToken());
//        Stack<Integer> s = new Stack<>();
//        st = new StringTokenizer(br.readLine());
//        for (int i = 0; i < n; i++){
//            s.push(Integer.valueOf(st.nextToken()));
//        }
//        StringBuffer sb = new StringBuffer();
//        int[] arr = new int[n];
//        int max = s.pop();
//        arr[n-1] = -1;
//        for (int i = n-2; i>= 0; i--){
//            int tmp = s.pop();
//            if (tmp>max){
//                arr[i] = -1;
//                max = tmp;
//            }else{
//                arr[i] = max;
//            }
//        }
//        for (int i = 0; i < n; i++){
//            System.out.print(arr[i] + " ");
//        }
//    }

    // 시간 초과
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        // 수열의 길이
        int n = Integer.parseInt(st.nextToken());
        Stack<Integer> s = new Stack<>();
        
        // 결과 값을 저장할 배열
        int[] arr = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++){
        	// 현재 값을 배열에 저장
            arr[i] = Integer.parseInt(st.nextToken());
            
            // 스택이 비어있지 않고, 스택의 top값이 현재 값보다 작다면
            while(!s.isEmpty() && arr[s.peek()] < arr[i]){
            	// 스택의 탒을 pop하고 top인덱스의 값을 현재 값으로 바꿔주기
                arr[s.pop()] = arr[i];
            }
            
            // 현재 인덱스를 스택에 저장
            s.push(i);
        }
        
        // 반복문이 끝나도 남아 있다는 말은 오큰수가 없다는 뜻이므로 모두 -1로 수정
        while (!s.isEmpty()){
            arr[s.pop()] = -1;
        }
        
        // 모든 결과 값을 출력해야 하므로 BufferedWriter활용
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < n; i++){
        	// 반복문마다 출력을 하는 것은 자원의 낭비가 심해져 시간 초과 발생
//            System.out.print(arr[i] + " ");
            bw.write(arr[i] + " ");
        }
        bw.flush();
    }
}

리뷰

1. 처음에는 스택으로 값을 모두 저장하고 끝에서부터 하나씩 pop을 하면서 해당 값을 오큰수로 지정하고, 두번째 pop부터 지정된 오큰수와 비교해서 만약 해당 값이 오큰수보다 크다면 -1을 저장하고, 해당 값을 오큰 수로 지정하면 되는거 아닌가 하는 생각으로 문제를 풀었다.
   그런데 오큰수는 현재 위치 arr[i]의 값보다 오른쪽에 있는 큰 수 중에 가장 왼쪽에 있는 수를 말하는 것인데, 위의 방법으로 풀이를 하니, 숫자의 위치는 상관없이 반복문 진행에 따라 최대값이 오큰수로 지정하는 문제가 있었다.

2. 그래서 두번째 풀이에서는 아예 스택에 인덱스 값을 저장을 하고, peek()메서드를 이용해 arr[stack.peek()]한 값이 현재 인덱스의 값 arr[i]보다 작으면 해당 값을 arr[i]/오큰수로 지정한다.
   이 풀이에서 포인트는
   1. 스택에 실제 값이 아닌 인덱스 값을 저장하는 것
   2. 만약 스택이 비어있지 않고 스택의 top값보다 현재 값이 크면, 스택에서 pop을 하고 해당 위치에 현재 값을 저장해 주는 것
   3. 반복문을 빠져나온 이후에 남아있는 값들은 오큰수가 없다는 뜻이므로 스택이 빌 때까지 값들을 -1로 바꿔주는 것
   4. System.out.println이 아니라 BufferedWriter를 활용할 것