백준23740 - 정렬, 그리디, 스위핑 기본문제

import java.util.*;
import java.io.*;
public class 버스노선23740 {
    static int N;
    static int[][] input;

    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        input = new int[N][3];
        for(int i = 0; i<N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            input[i] = new int[]{s,e,c};
        }

        Arrays.sort(input, Comparator.comparingInt(a->a[0]));
        ArrayList<int[]> rst = new ArrayList<>();
        int cs = input[0][0];
        int ce = input[0][1];
        int cc = input[0][2];

        for(int i = 1; i<N; i++){
            int ns = input[i][0];
            int ne = input[i][1];
            int nc = input[i][2];

            if(ns <= ce){
                ce = Math.max(ce, ne);
                cc = Math.min(cc, nc);
            }
            else {
                rst.add(new int[]{cs, ce, cc});
                cs = ns;
                ce = ne;
                cc = nc;
            }
        }

        //막구간 추가
        rst.add(new int[]{cs,ce,cc});

        StringBuilder sb = new StringBuilder();
        sb.append(rst.size()).append("\n");
        for(int[] r : rst){
            sb.append(r[0]).append(" ").append(r[1]).append(" ").append(r[2]).append("\n");
        }
        System.out.print(sb);
    }
}

 

정리

겹치는 노선들을 모두 합쳐서 하나의 노선으로 만들고 겹치는 노선이 있을때 그 중 가장 적은 금액으로 해당 노선의 금액을 설정할 때 전체 노선의 갯수와 출발점이 작은 순서대로 모든 노선의 정보를 출력하는 문제

약간 회의실 배정같은 문제임.

 

풀이 : 스위핑

입력을 일단 배열로 받고 출발지점을 오름차순으로 입력 배열을 정렬함

그러면 정렬 기준에 의해 겹침 기준은 다음 시작점 <= 현재 끝점 임

이를 만족한다면 겹친다는 것이므로 현재 끝점을 다음 끝점과 현재 끝점중 큰걸로, 현재 cost를 현재 cost와 다음 cost중 작은걸로

만족하지 않는다면 현재의 정보들은 다음에 영향을 미치지 않고 처리가 끝났으므로

List<int> result에 add 하고 curStart, curEnd, curCost를 nextStart, nextEnd, nextCost로 업데이트한다.

 

주의점

마지막에 현재 curCost, curEnd, curCost를 result에 꼭 삽입해야함

 

시간복잡도

정렬 (내부적으로는 TimSort 방식이므로 O(NlogN)) + 스위핑 (O(N)

= O(N log N)