[BOJ/Java] 21279 광부 호석

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	237	74	33	20.625%

문제

N 개의 광물이 있다. i 번째 광물은 (Xi , Yi )에 있으며 캐내는 비용은 1이고, 이것의 아름다운 정도는 Vi 이다.

호석이는 지금 (0, 0)에 있다. 타고난 광부인 호석이는 시그니쳐 스킬인 "광산 뒤집기"를 쓰려고 한다. 이 스킬을 쓰면 자신이 있는 위치를 꼭지점으로 하며, 원하는 높이 H(H ≥ 0), 너비 W(W ≥ 0) 인 직사각형 영역 안에 있는 모든 광물을 캘 수 있다. 영역의 테두리에 존재하는 광물도 캐야한다.

주의할 점은, 직사각형 영역 안에 들어오는 광물은 무조건 캐야 하며, 영역에 속한 광물들의 캐내는 비용의 총합이 현재 가진 돈 C 보다 크면 파산을 하게 된다.

호석이가 파산하면 광물을 못 캐고, 이로 인해 상상을 초월하는 나비효과가 발생해서 한국의 취직율이 떨어진다!!!!!!! 대신 호석이가 얻을 수 있는 광물들의 아름다운 정도의 합이 높아질수록 한국의 취직율은 올라간다!!!!!!!! 모두의 행복을 위해서 호석이가 파산하지 않고 얻을 수 있는 광물들의 아름다운 정도를 최대화하자.

입력

첫 줄에 광물의 개수 N 과 호석이가 가진 돈 C 가 주어진다.

이어서 N개의 줄에 걸쳐서, i번째 줄에 3개의 정수 Xi , Yi , Vi 가 주어진다. 각 숫자는 i 번째 광물이 위치한 X, Y 좌표와 아름다운 정도를 의미한다.

출력

호석이가 파산하지 않으면서 얻을 수 있는 광물들의 아름다운 정도의 합의 최댓값을 출력하라.

제한

1 ≤ N ≤ 500,000

0 ≤ Xi , Yi ≤ 100,000

1 ≤ Vi ≤ 108

1 ≤ C ≤ N

광물들은 모두 서로 다른 위치에 존재하며, (0, 0) 에는 광물이 존재하지 않음이 보장된다. 주어지는 모든 수는 정수이다.

예제 입력 1 복사

5 3
1 10 10
2 4 1
3 8 10
4 5 5
5 7 6

예제 출력 1 복사

21

예제 입력 2 복사

4 2
1 1 1
1 4 1
4 1 1
4 4 1

예제 출력 2 복사

2

풀이

 류호석 알고리즘 코딩 테스트의 가장 마지막 문제인 5번 문제였다.

 결론부터 말하자면 우선순위 큐를 사용하였다. 하지만 문제를 풀 때 우선순위 큐를 적용하는 과정에서 문제가 발생하였고 이에 대해서 먼저 이야기하고자 한다.

 

 문제 풀이 방향에 대한 접근성이 문제였다. 일단 문제에서 직사각형의 한 꼭지점이 원점으로 고정되어있기 때문에 직사각형의 범위를 결정하는 좌표는 한 좌표가 될 수 있다. 이때 그 좌표는 굳이 (0,0) 부터 (100000, 100000) 까지의 모든 좌표를 검색하지 않더라도 주어진 광물의 위치로 좌표를 잡았을 때 문제에서 나오는 예시에 대한 모든 경우를 포용할 수 있다.

 단, 광물을 캘 수 있는 갯수가 한정되어있기 때문에 광물 좌표를 검색하는 순서에 대한 우선순위를 결정하는 것이 필요했다. 이때 생각한 것이 첫번째 에러사항이다.

 광물을 input으로 받아 저장한 List를 x좌표가 작은 순 > y좌표가 작은 순으로 sorting을 먼저 진행하였다. 그 후 Comparable에서 y축이 높은 순으로 저장하는 우선순위 큐를 하나 더 만들어 여기에 하나하나 순서대로 넣으면서 광물을 캘 수 있는 갯수가 넘어갈때마다 우선순위 큐에서 하나씩 값을 빼가면서 검사했다.

Collections.sort(dia, new Comparator<index>() {
    @Override
    public int compare(index o1, index o2) {
        if(o1.x==o2.x) return o1.y - o2.y;
        return o1.x - o2.x;
    }
});

 현재 들고있는 대기 List에서 y좌표가 가장 높은 녀석이 직사각형의 높이를 결정짓는 존재이기때문에 처음 설계는 이렇게 지정하였다.

 문제는 이렇게 진행하였을 때 같은 x좌표 선상에 있는 좌표가 여러개 나와있을 때 이걸 제거하는 과정에서 실수가 발생했다.

예제 2번에서 만약 내가 가질 수 있는 광물이 3개가 가능할 경우일 지라도 해당 문제에서 가질 수 있는 직사각형은 다음 밖에 없다.

3개를 다 포함하는 직사각형은 만들 수 없다.

 3개의 광물을 가지고 싶어도 어쩔 수 없이 4개의 광물을 포함하게 되기 때문에 지금 만들 수 있는 최대 직사각형은 이렇게 총 2가지(작은 직사각형 1개는 제외한다).

 근데 앞서 만들었던 알고리즘에 따르면 하나하나씩 검토해서 들어가기 때문에 왼쪽 x좌표의 두 광물을 비교한 후 오른쪽 x좌표의 아래 광물(4,1)을 검사하게 되므로 (4,4)때문에 만들수 없을지라도 이를 검토하는 과정이 없기 때문에 냅다 3개가 다 된다고 허용하게 되어버린다.

하나하나씩 검사를 하게 될 경우 같은 x좌표에 광물이 있을 경우 검사하는데 있어서 매우 까다로웠기 때문에 이를 해결하는 방법을 찾기가 힘들었다.

 

 따라서 하나씩 체크한다는 접근성 자체를 바꾸어버렸다.

 입력을 받게 될 때 List 배열을 만들어 모든 x좌표에 따라서 가진 점에 대한 List를 받게끔 했다.

public static ArrayList<index>[] xIndex;

xIndex = new ArrayList[100005];
for(int i=0; i<xIndex.length; i++){
    xIndex[i] = new ArrayList<>();
}
for(int i=0; i<N; i++){
    st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());
    long value = Long.parseLong(st.nextToken());
    xIndex[x].add(new index(x, y, value));
}

 우선순위 큐는 현재 가지고 있는 직사각형에 들어있는 광물을 포함하며 y축의 높이를 기준으로 우선순위를 잡도록 했다. 결국 x축이 진행될 수록 허용하는 광물의 개수가 넘어가게된다면 y축 높이가 높은 것부터 날아가야하기 때문에 이를 제거하기 위한 용도이다.

 이전과 비슷할 수 있겠지만 x축을 검사할 때부터 다르다. x축을 넘어갈 때, 해당 x축에 있는 광물의 좌표를 허용하는 광물의 개수를 신경쓰지않고 우선순위 큐에 일단 모두 집어넣는다.

for(int i=0; i<xIndex.length; i++){
    if(xIndex[i].isEmpty()) continue;
    for(int j=0; j<xIndex[i].size(); j++){
        queue.add(xIndex[i].get(j));
        currentV += xIndex[i].get(j).value;
    }

 일단 현재 우선순위 큐에 들어있던 광물과 상관없이 새로운 x축에 대한 모든 광물이 들어오게 된다. 그 다음으로 허용하는 광물의 개수인 C가 넘어섰을 때의 작업을 진행해준다.

 광물의 제거는 지금 현재 가지고 있는 우선순위 큐의 광물에서 제한된 개수로 떨어질 때까지 가장 높은 광물을 제거하게된다. 단 여기서 문제는 같은 y좌표에 있는 광물에 대한 주의가 필요하다.

y좌표를 내려오면서 3개까지 지웠다해도 그 높이의 좌표가 또 있을 경우 직사각형을 만들 수 없다.

 지금과 같은 예에서 광물의 제한 갯수가 3개라고 했을 때 같은 y축의 광물에 대한 주의가 없다면 x=2의 경우에서 (3,2)와 (2,2)를 제거하면 (1,2)는 남아있지만 이미 갯수가 3개를 충족했기 때문에 직사각형을 만들 수 없음에도 불구하고 제거기능을 마무리하게 된다. 따라서, 이전에 제거한 좌표의 y축에 대해서 값을 저장한 후 보유한 개수에 상관없이 큐의 peek값이 y축과 같다면 이를 제거해주는 과정이 필요하다.

 즉, x=2좌표에 다다랐을 때 우리가 해야할 일은 허용 갯수까지 광물을 다빼는것과 제거하는 과정에서 제거된 광물과 높이가 같은 광물은 제거하는것을 해야하는 것이다.

int prevTop = -1;
while(!queue.isEmpty() && queue.size()>C){
    prevTop = queue.peek().y;
    currentV -= queue.poll().value;
    while(!queue.isEmpty() && queue.peek().y == prevTop){
        currentV -= queue.poll().value;
    }
}

 

 이 과정이 다음 x좌표를 도달했을 때 진행하는 한번의 사이클로 한번의 사이클이 끝났다면 현재 V값을 비교해서 가장 높은 값을 저장해두고 다음 x좌표 사이클로 돌아간다.

 결국 우선순위 큐를 사용하는 것은 같지만 검사를 하는 과정에서 모든 광물을 한개씩 검사하느냐, x좌표에 있는 모든 광물을 받아내서 한꺼번에 검사를하느냐의 차이이다. 전자의 경우로도 물론 가능하게 짤 수 있겠지만 말했다시피 하나하나씩 List를 검사했기 때문에 같은 x좌표 선상에 있는 광물을 검사해야하는 현재 문제의 특성상 같은 x좌표를 한꺼번에 처리하는 것이 나아보인다고 생각한다.

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static int N, C;
    public static ArrayList<index>[] xIndex;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        xIndex = new ArrayList[100005];
        for(int i=0; i<xIndex.length; i++){
            xIndex[i] = new ArrayList<>();
        }
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            long value = Long.parseLong(st.nextToken());
            xIndex[x].add(new index(x, y, value));
        }
        long answer = 0;
        long currentV = 0L;
        PriorityQueue<index> queue = new PriorityQueue<>();
        for(int i=0; i<xIndex.length; i++){
            if(xIndex[i].isEmpty()) continue;
            for(int j=0; j<xIndex[i].size(); j++){
                queue.add(xIndex[i].get(j));
                currentV += xIndex[i].get(j).value;
            }
        int prevTop = -1;
        while(!queue.isEmpty() && queue.size()>C){
            prevTop = queue.peek().y;
            currentV -= queue.poll().value;
            while(!queue.isEmpty() && queue.peek().y == prevTop){
                currentV -= queue.poll().value;
            }
        }
            answer = Math.max(answer, currentV);
        }
        System.out.println(answer);
    }
    public static class index implements Comparable<index> {
        int x;
        int y;
        long value;

        public index(int x, int y, long value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }

        @Override
        public int compareTo(index o) {
            return o.y - this.y;
        }
    }

}