[BaekJoon] 14427 수열과 쿼리 15 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/14427

2.  문제

요약

• 길이가 N인 수열 $A_1, A_2, ..., A_N$이 주어질 때 다음 쿼리를 수행하는 문제입니다.
  • 1 i v : $A_i$를 v로 변경합니다.
    • i는 1 이상 N 이하의 수이고, v는 1 이상 $10^9$ 이하의 수입니다.
  • 2 : 수열에서 크기가 가장 작은 값의 인덱스를 출력합니다. 그러한 값이 여러 개라면 인덱스가 작은 것을 출력합니다.
• 수열의 인덱스는 1부터 시작합니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 수열의 크기 N이 주어지고 두 번째 줄에 1보다 크거나 같고 $10^9$보다 작거나 같은 $A_1, A_2, ..., A_N$이 주어지며 세 번째 줄에 1보다 크거나 같고 100,000보다 작거나 같은 쿼리의 개수 M이 주어지고 네 번째 줄부터 M개의 줄에 쿼리가 주어집니다.
• 출력: 2번 쿼리에 대해서 정답을 하나씩 한 줄에 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
import java.util.TreeMap;

public class Main {
    static StringBuilder sb = new StringBuilder();
    static int N, M;
    static TreeMap<Integer, PriorityQueue<Integer>> map;
    static int[] series;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        series = new int[N + 1];
        map = new TreeMap<>();

        for(int idx = 1; idx <= N; idx++) {
            int num = scanner.nextInt();
            if(!map.containsKey(num)) map.put(num, new PriorityQueue<>());
            map.get(num).add(idx);
            series[idx] = num;
        }

        M = scanner.nextInt();
        for(int query = 1; query <= M; query++) {
            int queryType = scanner.nextInt();
            if(queryType == 1) {
                int idx = scanner.nextInt(), newValue = scanner.nextInt();
                int originalValue = series[idx];

                series[idx] = newValue;

                PriorityQueue<Integer> idxList = map.get(originalValue);
                idxList.remove(Integer.valueOf(idx));
                if(idxList.isEmpty()) map.remove(originalValue);

                if(!map.containsKey(newValue)) map.put(newValue, new PriorityQueue<>());
                map.get(newValue).offer(idx);
            } else if(queryType == 2) {
                Map.Entry<Integer, PriorityQueue<Integer>> firstEntry = map.firstEntry();
                sb.append(firstEntry.getValue().peek()).append('\n');
            }
        }
    }

    public static void main(String[] args) {
        input();
        System.out.print(sb);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 수열의 각 수를 key로, 각 수의 인덱스들을 value로 갖는 TreeMap을 생성합니다.
  • 쿼리 2가 들어오면 가장 작은 값의 인덱스를 출력해야 하기 때문에 키가 정렬되어있어야 하므로 TreeMap을 이용합니다.
  • 또한, 만약 가장 작은 값이 여러 개라면 가장 인덱스가 작은 것을 출력해야 하기 때문에 인덱스 역시 정렬되어있어야 하므로 PriorityQueue를 이용하여 인덱스들을 저장합니다.
• 주어진 수열을 TreeMap에 알맞게 넣고, series라는 1차원 배열에 수열을 저장합니다.
• 주어진 쿼리들에 맞춰 쿼리를 수행합니다.
  • 만약 쿼리가 1에 해당한다면
    • 변경할 인덱스와 변경될 값을 입력받습니다.
    • series에서 수열에서의 해당 인덱스 값을 찾아 해당 값의 인덱스들이 들어있는 PriorityQueue를 가져오고 PriorityQueue에서 해당 인덱스를 제거합니다.
    • 만약 해당 인덱스를 제거했을 때 PriorityQueue가 비어있다면 해당 Entry를 TreeMap에서 제거합니다.
    • series의 해당 인덱스 값을 변경될 값으로 변경하고 TreeMap에 변경될 값이 key로 들어있지 않다면 TreeMap에 변경될 값을 key로 하는 Entry를 하나 추가합니다.
    • 그리고 변경될 값을 key로 하는 Entry의 value(PriorityQueue)에 해당 인덱스를 추가합니다.
  • 만약 쿼리가 2에 해당한다면
    • key가 정렬되어있기 때문에 TreeMap의 첫 번째 Entry를 가져와 해당 Entry의 value인 PriorityQueue에서 값 하나를 peek하여 출력합니다.