ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • BOJ 17299 오등큰수 풀이를 통한 자료구조에 담을 정보에 대한 회고
    알고리즘 문제풀이/Java 2020. 4. 14. 00:14

     

     

    문제

    크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.

    Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.

    예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1이다. NGF(4) = 2, NGF(5) = 2, NGF(6) = 1 이다.

    입력

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

    출력

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

    예제 입력 1 복사

    7 1 1 2 3 4 2 1

    예제 출력 1 복사

    -1 -1 1 2 2 1 -1


    해설

     

    import java.io.*;
    import java.util.Stack;
    
    public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
            int N = Integer.parseInt(br.readLine());
            String[] arr = br.readLine().split(" ");
            int[] freq = new int[1000000];
            for(int i = 0; i < arr.length; i++){
                freq[Integer.parseInt(arr[i])]++;
            }
    
            Stack<Integer> stack = new Stack<>();
            stack.push(0);
            for(int i = 1; i < N; i++){
                if(stack.isEmpty()){
                    stack.push(i);
                }
                while(!stack.isEmpty() && freq[Integer.parseInt(arr[stack.peek()])] < freq[Integer.parseInt(arr[i])]){
                    arr[stack.pop()] = arr[i];
                } 
                stack.push(i);
            }
            while(!stack.isEmpty()){
                arr[stack.pop()] = "-1";
            }
    
            for(String str: arr){
                wr.write(str + " ");
            }
            wr.flush();
        }
    }
    

     

    문제의 접근에 대한 회고

     

     idx로 저장해야하는 까닭은 stack에 원 배열의 값을 집어 넣게 되면, 당장 양 사이드 idx의 값들은 비교가 가능하지만, idx 차가 2이상 나버리면 stack에 저장되어 있는 값과 비교만 가능할 뿐, 원 배열의 수를 변경시켜줄 수가 없다. 그렇기 때문에 idx로 저장해야한다.
    stack의 특성(가장 위에 있는 요소의 정보만 알 수 있다)을 생각하면, idx를 저장하는 게 더 효율적이다.
    오등큰수 문제의 경우, 기존 배열을 freq(빈도수)로 치환하여 생각하면, 오큰수문제와 논리는 같다는 걸 확인할 수 있다. 대신 비교를 통해 배열의 값을 바꿔줄 때, freq 배열이 아닌, 원 배열의 값을 변화시켜줘야 하기 때문에, 중간에서 변환 과정이 이루어져야 한다.
    즉, idx => arr[idx] => freq[arr[idx]] 이러한 과정이 이루어져야 한다.

     

    느낀 점

    • 처음 이 문제의 하위버전인 오큰수를 해결할 때, 배열의 값만 저장하려고 했다. 하지만 배열의 값을 스택에 저장한다는 건, 더 이상 해당 배열의 정보가 필요하지 않다는 걸 의미하는데, 이 문제의 경우 원배열의 값을 변화시켜줘야 하기 때문에 idx를 저장하는 게 옳은 풀이이다. 이렇게 그저 문제를 해결하려고 하지말고, 데이터를 어떠한 자료구조에 어떠한 정보를 저장할 지 고민하는 습관이 필요할 것 같다.

     

     

    댓글

Designed by Tistory.