[BOJ] 2170: 선 긋기 (JAVA)

문제

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

 

여담

이 문제는 강의실 배정 문제와 비슷하다고 느꼈다. 그래서 그때 풀었던 방식을 기반으로 생각해서 풀었더니 한 번에 맞았다! 정답률이 조금 높을 걸 보니 어려운 문제는 아닌 것 같지만 그래도 조금 뿌듯했다.

 

그치만 다른 풀이를 참고했더니 굳이 연결된 선의 정보를 저장하지 않아도 된다는 것을 알게 되었다. 풀이를 보면 아 그러네..! 라는 생각이 들지만 왜 막상 풀 때는 생각나지 않을까😂

 

풀이

문제의 핵심은 이미 선이 그려진 위치에 다시 선을 그을 수 있다는 점이다. 즉, 이미 그어진 선과 연결해서 새로운 선을 그을 수 있으므로 이미 그은 선과 현재 그을 선이 겹치는지 판별하는 것이 중요하다.

 

이미 그은 선과 현재 그을 선이 겹치는 경우는 다음과 같다.

• 현재 그을 선의 x 좌표 ≤ 이미 그어진 선의 y 좌표
  • 이미 x 좌표를 기준으로 오름차순 정렬했기 때문에, 현재 그을 선은 이미 그어진 선의 x 좌표보다 무조건 작거나 같음
  • 따라서 이미 그어진 선의 y 좌표랑만 비교하면 됨

 

만약 선을 이어서 그을 수 없다면 현재까지 그린 선의 길이를 저장하고, 이미 그어진 선의 x, y 값을 갱신하면 된다.

• 현재까지 그린 선의 길이 = startY - startX
• 이미 그어진 선의 x, y 값 갱신하기
  • startX = lines[i].x
  • startY = lines[i].y

 

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Line[] lines = new Line[n];
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            lines[i] = new Line(x, y);
        }
        Arrays.sort(lines, (l1, l2) -> {
            /// x를 기준으로 오름차순 정렬 (앞에서부터 선을 그릴 것이므로)
            if (l1.x == l2.x) return l1.y - l2.y;
            return l1.x - l2.x;
        });

        int startX = lines[0].x, startY = lines[0].y;
        int total = 0;
        for (int i = 1; i < n; i++) {
            if (lines[i].x <= startY) { // 선을 연속해서 그을 수 있는 경우
                startY = Math.max(startY, lines[i].y);
            } else {
                total += startY - startX;
                startX = lines[i].x;
                startY = lines[i].y;
            }
        }
        total += startY - startX;
        System.out.println(total);
    }

    static class Line {
        int x, y;

        public Line(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

---