[자바] 백준 23740 - 버스 노선 개편하기 (java)

목차

문제 : boj23740

 

 

필요 알고리즘

• 정렬, 스위핑
  
  • 스위핑을 통해 풀 수 있는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

1.  겹친다는 부분을 어떻게 알 수 있을까?

노선A의 e가 노선 B의 s 이상이고, 노선 B의 e가 노선 A의 s 이상이라면 겹친다고 볼 수 있을 것이다.

이 때, 무조건 s가 증가하는 순서대로 정렬해두고 확인해본다고 해보자. s가 더 작은 쪽이 노선 A라고 한다면 이후 겹친다는 판단은 노선A의 e가 노선B의 s 이상인지만 판단하면 된다. (s가 증가하는 순서대로 확인 중이므로 노선 B의 e가 노선 A의 s 이상임은 언제나 만족함)

 

2.  그렇다면 두 노선이 겹친다면 합쳐야 하는데, 합친다면 어떤 일이 일어나야 할까?

두 노선 A와 노선 B를 합칠 경우 새로운 노선 C는 A와 B 중 작은 s값, A와 B 중 큰 e값, A와 B 중 작은 c 값을 가지는 새로운 노선이 될 것이다. 마찬가지로 s가 증가하는 순서대로 보고 있으므로, e와 c만 판단하면 된다.

 

3.  노선이 겹치지 않을 경우엔 이전까지 합쳐진 노선을 출력해주면 끝이다.

 

 

  이걸 코드로 보면 아래와 같다.

Collections.sort(routes, (r1, r2) -> r1.s==r2.s ? r2.e-r1.e : r1.s-r2.s);	// s가 증가하는 순서로 확인

List<Route> reorganizationRoutes = new ArrayList<>();
Route routeTmp = new Route(-1 ,-1, Integer.MAX_VALUE);
for (Route route : routes) {
    if (routeTmp.e < route.s) {	// 노선이 겹치지 않는다면
        reorganizationRoutes.add(routeTmp);	// 결과로 출력해준다.
        routeTmp = route;	// 다음 합쳐진 노선을 확인해봐야하니 현재 노선의 정보를 키핑한다.
        continue;
    }

	// 이하 노선이 겹치는 경우이다.
    routeTmp.e = max(routeTmp.e, route.e);	// e는 둘 중 큰 값
    routeTmp.c = min(routeTmp.c, route.c);	// c는 둘 중 작은 값
}
reorganizationRoutes.add(routeTmp);	// 다 본 후에 남아있는 노선도 출력해준다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

import static java.lang.Math.max;
import static java.lang.Math.min;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        List<Route> routes = new ArrayList<>();
        while (n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            routes.add(new Route(s, e, c));
        }

        Collections.sort(routes, (r1, r2) -> r1.s==r2.s ? r2.e-r1.e : r1.s-r2.s);

        List<Route> reorganizationRoutes = new ArrayList<>();
        Route routeTmp = new Route(-1 ,-1, Integer.MAX_VALUE);
        for (Route route : routes) {
            if (routeTmp.e < route.s) {
                reorganizationRoutes.add(routeTmp);
                routeTmp = route;
                continue;
            }

            routeTmp.e = max(routeTmp.e, route.e);
            routeTmp.c = min(routeTmp.c, route.c);
        }
        reorganizationRoutes.add(routeTmp);

        StringBuilder sb = new StringBuilder();
        sb.append(reorganizationRoutes.size()-1).append('\n');
        for (int i = 1; i < reorganizationRoutes.size(); i++) {
            sb.append(reorganizationRoutes.get(i).toString());
        }

        System.out.print(sb);
    }
}

class Route {
    int s, e, c;

    public Route(int s, int e, int c) {
        this.s = s;
        this.e = e;
        this.c = c;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(s).append(' ').append(e).append(' ').append(c).append('\n');
        return sb.toString();
    }
}