백준 2170 문제

풀이

첫 번째 시도

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static class Line {
        int start;
        int end;
        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        ArrayList<Line> alist = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            alist.add(new Line(in.nextInt(), in.nextInt()));
        }

        Collections.sort(alist, (l1,l2)-> {
            if(l1.start==l2.start) {
                return l1.end-l2.end;
            } 
            return l1.start-l2.start;
        });

        
        Line line = alist.get(0);
        int start = line.start, end = line.end;
        int totalLength = line.end-line.start;

        for(int i = 0; i < N; i++) {
            line = alist.get(i);
            if(line.start >= start && line.start <= end) {
                if(line.end > end) {
                    totalLength += (line.end-end);
                    end = line.end;
                } 
            } else {
                start = line.start;
                end = line.end;
                totalLength += (end-start);
            }
        }
        System.out.println(totalLength);
        in.close();
    }
}

1. 선의 시작점을 기준으로 오름차순한다.
2. 시작점이 같다면 끝나는 지점을 기준으로 오름차순한다.
3. 정렬된 선들을 순차탐색하며 최종 길이를 구한다.
   • 초기 기준 선은 가장 첫 번째 선으로 설정한다.
     3-1. 만일 현재 선이, 기준 선에 모두 겹친다면 길이를 더하지 않는다.
     3-2. 일부만 겹친다면, 겹치지 않는 길이를 더한다.
     3-3. 전혀 겹치치 않는다면 현재 선의 전체 길이를 더하고, 기준 선을 현재 선으로 바꾼다.

위와 같이 코드를 짰더니 시간초과가 떴다.
다른 사람들 코드를 들여다봐도 나랑 특별히 차이가 있는 것 같지는 않았다.
일단 입력을 받기 위해 O(N), 정렬하는 데 O(NlogN), 그리고 최적해를 찾는 데에 O(N) ... 결국 O(N+NlogN)으로 통과한 남들처럼 O(NlogN)의 시간복잡도를 갖는 코드이다. 근데 왜 시간초과가 나는 걸까 ...

(+) 입력을 받는 부분밖에 다른게 없어서 Scanner를 BufferedReader로 바꾸어 보았다. 그랬더니 통과함 ....... 다들 BufferedReader를 쓰는 이유가 있구나 .... Scanner가 익숙하고 쉬워서 계속 습관처럼 쓰고 있었는데 역시 PS 할 땐 BufferedReader가 답인가보다.

최종 제출 코드

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

public class Main {
    static class Line {
        int start;
        int end;
        public Line(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        ArrayList<Line> alist = new ArrayList<>();
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            alist.add(new Line(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        Collections.sort(alist, (l1,l2)-> {
            if(l1.start==l2.start) {
                return l1.end-l2.end;
            } 
            return l1.start-l2.start;
        });

        
        Line line = alist.get(0);
        int start = line.start, end = line.end;
        int totalLength = line.end-line.start;

        for(int i = 0; i < N; i++) {
            line = alist.get(i);
            if(line.start >= start && line.start <= end) {
                if(line.end > end) {
                    totalLength += (line.end-end);
                    end = line.end;
                } 
            } else {
                start = line.start;
                end = line.end;
                totalLength += (end-start);
            }
        }
        System.out.println(totalLength);
    }
}