[BOJ] 2170 - 선 긋기

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/2170

2170번: 선 긋기

난이도: 골드 5

사용언어: JAVA

 

풀이

시작점과 도착점에 대한 입력을 받아 시작점의 위치를 기준으로 오름차순 정렬만 할 수 있다면, 이미 문제를 푼 것이나 다름이 없습니다. 정렬을 해두었다면 그냥 선을 하나씩 확인하면서 현재 그려지고 있는 선과 분리된 것인지 또는 겹쳐지는 것인지를 판단하고, 그어진 선의 총 길이를 계산해주기만 하면 됩니다.

 

코드의 주석을 확인하는 것이 더 이해하기에 편하실 것 같습니다. 

 

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];
        int last; // 현재 선의 마지막 지점을 저장
        int sum; // 현재까지의 선의 길이를 저장
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(arr, new Comparator<int[]>() { // 시작점을 기준으로 오름차순 정렬
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0])
                    return o1[1] - o2[1];
                else
                    return o1[0] - o2[0];
            }
        });
 
        last = arr[0][1]; // 처음에는 첫 번째 긋는 선의 끝 지점이 현재까지의 마지막 지점
        sum = arr[0][1] - arr[0][0]; // 처음에는 첫 번째 긋는 선의 길이가 현재까지의 총 길이
 
        for (int i = 1; i < N; i++) {
            if (arr[i][0] <= last) { // 새로운 선이 현재의 선과 겹쳐진다면,
                if (arr[i][1] >= last) // 새로운 선이 현재의 선에 완전히 포함되는 경우가 아니라면
                    sum += arr[i][1] - last; // 길이의 총합에 추가되는 부분을 합산
                else
                    continue; // 새로운 선이 현재의 선에 완전히 포함된다면, 그냥 다음 선으로 넘어가면 됨
            } else {
                sum += arr[i][1] - arr[i][0]; // 현재의 선과 완전히 별개의 선이라면, 해당 선의 길이를 총합에 합산
            }
            last = arr[i][1]; // 현재 선의 마지막 부분을 업데이트
        }
        bw.write(String.valueOf(sum)); // 최종 총합 출력
        bw.flush();
        bw.close();
        br.close();
    }
}