Skip to content

Latest commit

 

History

History
129 lines (85 loc) · 4.93 KB

No.17298.md

File metadata and controls

129 lines (85 loc) · 4.93 KB

백준_qorwns_Beakjoon 백준 17298s번 문제 : https://www.acmicpc.net/problem/17298



백준 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. 다음에 있는 인덱스의 숫자가 더 큰 경우 -> 바로 반환

  2. 더 작은수가 반복되다가 더 큰수를 만난 경우 -> 작은수의 횟수 만큼 큰수를 찍어내기

  3. 작은수만 나오다가 끝난 경우 -> -1 반환하기

위 분기점의 2번 조건 때문에 스택을 이용해서 값을 처리하는 방법이 좋아보인다. 스택으로 위 분기점에 따른 행동을 생각해보면

  1. 스택에 현재값을 빼고 큰 수를 반환한 뒤 그 값을 넣는다.
  2. 비어있지 않고 작은수가 나왔다면 스택에 계속 집어넣고 큰 수가 나왔다면 작은 동안 반환하다가 큰 수에서 멈추고 큰 수를 스택에 넣는다.
  3. 빠지지 않고 남은 스택 값들을 -1로 반환한다.

3번 행동에서 -1을 반환할 위치를 특정하기 위해서 스택에 인덱스를 넣도록 하고 1,2번은 겹치는 내용이 있으므로 통합한다.

주어진 예제를 이용해서 자세하게 확인해보자

예제 1번.

주어진 배열 값은 3,5,2,7

  ( 0   데이터 출입부
    3   value

시작할 때 처음 값을 넣고 시작하고 바로 다음 값으로 5를 만나 5를 반환한 뒤 스택에 넣는다. 현재 반환 배열 5

  ( 1   데이터 출입부
    5   value

다음 값인 2는 그대로 스택에 들어가고 7을 만나 반복해서 스택에서 빼면서 7을 반환한뒤 스택에 넣는다. 현재 반환 배열 5,7,7

  ( 1 | 2   데이터 출입부        ->        ( 3   데이터 출입부
    5,  2   value            ->           7   value

끝으로 7보다 큰 오른쪽 인덱스가 없으므로 -1을 반환하고 스택에서 제거한다. 완료 반환 배열 5,7,7,-1

예제 2번.

주어진 배열 값은 9,5,4,8

  ( 0   데이터 출입부 
    9   value

시작할 때 값을 넣고 시작하고 작은 수들은 계속 집어넣는다. 현재 반환 배열

  ( 0 | 1 | 2   데이터 출입부
    9,  5,  4   value

8을 만나 8보다 작은 수들의 수 만큼 8을 반환하고 스택에 넣는다. 현재 반환 배열 null, 8, 8, null

  ( 0 | 3   데이터 출입부
    9,  8   value

남은 인덱스 값에 -1을 반환한다. 완료 반환 배열 -1, 8, 8, -1

알고리즘

        // 이 코드에서 초기화되지 않은 arr 는 주어진 배열의 값을 의미한다.

        int[] answer = new int[5];                              // 결과값
        Stack<Integer> st = new Stack<>();                      // 이용할 스택
        st.push(0);                                             // 첫 번째 값 입력

        for(int i=1;i<arr.length;i++){                          
            while(!st.isEmpty() && arr[st.peek()]<arr[i]){      // 비어있지 않고 현재 스택 맨위 값이 배열의 현재 값보다 작은 동안 
                answer[st.pop()]=arr[i];                        // 값을 빼내면서 큰 값을 반환
            }
            st.push(i);                                         // 큰 값의 인덱스 삽입
        }

        while(!st.isEmpty()){                                   // 비어있지 않은 동안
            answer[st.pop()]=-1;                                // -1을 반환하면서 빼냄
        }
        
        for(int i : answer){
            System.out.println(i+", ");            
        }