BOJ 17299 오등큰수 풀이를 통한 자료구조에 담을 정보에 대한 회고

문제

크기가 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를 저장하는 게 옳은 풀이이다. 이렇게 그저 문제를 해결하려고 하지말고, 데이터를 어떠한 자료구조에 어떠한 정보를 저장할 지 고민하는 습관이 필요할 것 같다.