본문으로 건너뛰기

3362 - Zero Array Transformation III

info

풀이 키워드​

스포주의

정렬 그리디 힙


풀이 코드​

info
  • 메모리: 114400 KB
  • 시간: 87 ms
class Solution {
    public int maxRemoval(int[] nums, int[][] queries) {
        // zero array를 만들 수 있는 최소 쿼리 수를 구하는 것으로 문제를 치환한다.
        int usedCnt = 0;
        int qdx = 0; // index of queries

        // 시작 지점 순으로 오름차순 정렬
        Arrays.sort(queries, (a, b) -> a[0] - b[0]);
        // 선택 가능한 녀석들의 종료 지점 (오래가는 순 정렬)
        PriorityQueue<Integer> availEnds = new PriorityQueue<>(Collections.reverseOrder());
        // 선택된 녀석들의 종료 지점 (빨리 끝나는 순 정렬)
        PriorityQueue<Integer> selectedEnds = new PriorityQueue<>();

        // 0이 아닌 칸 발견시 필요만큼 쿼리 선택
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] == 0) continue;

            // 이전에 선택한 쿼리 중 i 이전까지의 쿼리 제거
            while (!selectedEnds.isEmpty() && selectedEnds.peek() < i)
                selectedEnds.poll();
            
            // 선택 가능 쿼리 업데이트
            while (qdx < queries.length && queries[qdx][0] <= i)
                availEnds.add(queries[qdx++][1]);

            // 필요한 만큼만 최소한의 쿼리 선택
            int required = nums[i]; // i 지점의 요구 쿼리 수
            while (selectedEnds.size() < required) {
                if (!availEnds.isEmpty() && i <= availEnds.peek())
                    selectedEnds.add(availEnds.poll());
                else return -1; // 쿼리가 부족하면 -1
                ++usedCnt;
            }
        }

        return queries.length - usedCnt;
    }
}

풀이 해설​

지문에선 zero array를 만드는데 필수적이지 않은(=제거해도 zero array에 도달 가능한) 최대 쿼리 수를 반환하라고 했지만,

이는 zero array를 만들기 위한 최소한의 필요 쿼리 수를 구하는 것으로 치환할 수 있다.

이 때, 최대한 넓은 구간의 쿼리를 우선적으로 선택하는 것이 이득이라는 점에서 그리디 냄새가 나는 문제이다.

하지만 그리디한 방식으로 쿼리를 선택했을 때,
그 쿼리의 선택으로 인한 특정 nums 구간의 감산을 어떻게 처리할지에 대해서 일정 수준의 아이디어가 요구된다.


🎯 풀이 논리 설명​

WIP


메모​

  • 아니 이런 방법이?
  • 정렬이 필요하다는 것과 쿼리의 시작 인덱스는 오름차순, 종료 인덱스는 내림차순으로 정렬해야겠다는 것까진 스스로 생각이 났다. 문제는 그 다음이 생각 안남.
  • 아무리 봐도 medium 난이도는 아니고 hard에 가까운듯