[Baekjoon] 2170: 선 긋기

문제

선을 정해진 횟수만큼 긋고 최종 길이를 구하는 단순 스위핑 문제이다.

 

풀이

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Q2170 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        Queue<long[]> pq = new PriorityQueue<>(Comparator.comparingLong(c -> c[0]));
        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            pq.offer(new long[]{Long.parseLong(input[0]), Long.parseLong(input[1])});
        }

        long[] poll = pq.poll();
        long start = poll[0];
        long end = poll[1];

        long total = 0;
        while (!pq.isEmpty()) {
            long[] cur = pq.poll();
            long left = cur[0];
            long right = cur[1];
            if (left <= end) {
                if (right > end) {
                    end = right;
                }
                continue;
            }
            total += end - start;
            start = left;
            end = right;
        }
        total += end - start;

        System.out.println(total);
    }
}

최소힙에 값을 삽입하여 겹치면 계속 오른쪽 값을 갱신하고, 겹치지 않으면 총 길이에 더하여 좌우값을 다시 갱신하는 형식으로 구현했다.

처음에 계속 틀려서 이유를 확인해봤더니, 겹칠때 오른쪽 값이 기존 값보다 작다면 갱신하지 않아야된다는 조건을 생각하지 못했다..

 

예를 들어,

1 5

2 4

의 값이 들어온다면 최종적으로 1 5에 선이 그려져 길이는 4가 되야하지만

겹치면 오른쪽 값을 계속 갱신해버린 탓에 1 4가 최종 선이 되어 3이 되어버린 것이다.

 

스위핑 문제를 접하게 되면 이와 같은 예시는 주의하자

 

회고

스위핑 개념을 배운지 얼마되지 않아 반례 생각하는게 좀 힘들었던 것 같다.

좀 더 관련된 문제를 많이 풀어봐야겠다.