백준 2170번 <선 긋기>

백준 알고리즘 2170번

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

2170번: 선 긋기

---

2170번

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

---

문제 해결

그리디 알고리즘으로 해결했다.

 

문제를 푸는 로직을 찾는 건 어렵지 않았는데 시간초과를 해결하는데 시간을 좀 썼다.

선이 여러 번 그려질 수 있다는 것이 문제에 명시되어 있기 때문에 중복을 빼고 계산을 해주어야 시간초과가 나지 않는다.

 

문제를 해결하는 로직은 다음과 같다.

• 선을 긋는 시작 지점을 기준으로 오름차순 정렬을 진행한다.
• start에 1번째 선의 start를, end에 1번째 선의 end를 저장한다.
• 그 다음 나머지 선들을 순서대로 보며 다음과 같은 프로세스를 수행한다.
  • 만약 현재 선의 start가 end보다 작거나 같으면 겹치는 선이기 때문에 end의 값을 현재 선의 end 중 큰 값으로 업데이트한다.
  • 만약 현재 선의 start가 end보다 크다면 겹치지 않기 때문에 지금까지 그어진 선의 길이(end-start)를 누적시킨다. 그 다음에 start에 현재 선의 start를, end에 현재 선의 end를 저장한다.
• 마지막에 그어진 선의 길이(end-start)를 누적시킨다.

시간초과를 피하기 위해 시작 지점이 같은데 끝 지점이 다른 경우를 걸러주기 위해 HashMap을 사용해 key에 시작지점을, value에 끝 지점 중 가장 큰 값을 저장하여 중복을 없애주었다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class BOJ_2170 {
    static class Tuple{
        int start, end;

        public Tuple(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            String[] inArr = br.readLine().split(" ");
            int a = Integer.parseInt(inArr[0]);
            int b = Integer.parseInt(inArr[1]);
            int temp = map.getOrDefault(a, a);
            map.put(a, Math.max(temp, b));
        }

        ArrayList<Tuple> line = new ArrayList<>();
        for (Integer key : map.keySet()) {
            int temp = map.get(key);
            line.add(new Tuple(key, temp));
        }

        Collections.sort(line, (a, b) -> Integer.compare(a.start, b.start));


        int start = line.get(0).start;
        int end = line.get(0).end;
        int acc = 0;
        for (int i = 1; i < line.size(); i++) {
            if (end >= line.get(i).start) { // 겹침
                end = Math.max(line.get(i).end, end);
            } else {    // 안겹침
                acc += (end - start);
                start = line.get(i).start;
                end = line.get(i).end;
            }
        }
        acc += (end - start);
        System.out.println(acc);
    }
}

---

결과

---