[백준] 2170 - 선 긋기 | Java

📌 문제 정보

[2170: 선 긋기]

💡 접근 방식

LinkedList를 사용해야 하나? 주어진 선 범위는 visited 체크를 해야하나? 가 처음에 든 생각이다. 하지만 잘 생각해보면 전체 범위에 해당하는 배열을 만들어 선분을 표시하는 방식은 비효율적이다.

문제의 핵심은 겹치는 구간을 잘 처리해서 선분들의 총 길이를 구하는 것이다.
그래서 주어진 선분을 세 가지 경우로 나누었다.

1. 이미 그어진 선에 완전히 포함되는 경우
   -> 무시하면 된다.
2. 이미 그어진 선에 걸치는 경우
   -> 이전 y값과 현재 y값의 차를 더하면 된다.
3. 아예 새로운 선인 경우
   -> 그냥 해당 길이를 더하면 된다.

✅ 코드

import java.util.*;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        int[][] line = new int[n][2];


        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());
            line[i][0] = x;
            line[i][1] = y;

        }

        Arrays.sort(line, ((o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        }));

        int total = line[0][1] - line[0][0];
        int max = line[0][1];

        for (int i = 1; i < n; i++) {
            max = Math.max(max, line[i-1][1]);
            int x = line[i][0];
            int y = line[i][1];


            if (y >= max) {
                if (x > max) { // 아예 새로운 선
                    total += y - x;
                } else { // 이미 그어진 선 걸침
                    total += y - max;
                }
            }


        }

        System.out.println(total);

    }
}

🧠 배운 점 & 회고

항상 문제를 대충 읽고 손부터 나가는 습관이 있는 것 같다. 천천히 생각 정리를 하면 간단하게 풀 수 있는 문제임에도, "대충 이런 느낌이겠지~" 하며 풀다보면 점점 핵심을 놓치고 산으로 가게 되었다. 앞으로는 문제를 꼼꼼히 읽고, 요구하는 게 뭔지 정확히 파악하는 습관을 길러야겠다.

🧾 결과