코드트리 [자바 java] 서로 다른 구간의 수

https://www.codetree.ai/missions/8/problems/number-of-distinct-segments?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

https://ethereal-coder.tistory.com/142

코드트리 [자바 java] 가장 많이 겹치는 구간

이 문제와 비슷하지만, 이 문제에서는 겹치는 선분을 하나로 생각한다.

처음에 일반적인 -1+1테크닉으로 풀었을 때 런타임 에러가 났었는데 그 이유는 주어지는 점의 위치가 10^9일 수도 있기 때문이다. 이렇게 하면 메모리초과가 나기 때문에 배열이 아닌 ArrayList를 만들었다. 

 

우선 dot class를 만들었는데, 이 클래스는 해당 점의 위치, 시작,끝 여부, 선분의 index를 포함한다.dot로 선언한 list에 선분의 처음과 끝 점을 넣고 이를 정렬한다. (이를 위해서 dot class에 comparator를 넣는다.)

그 다음 이를 차례로 탐색하면서 탐색중인 index를 hashset에 넣고, hashset가 빈 상태로 새로운 시작 점을 만나면 답에 +1을 한다.

 

import java.io.*;
import java.util.*;
import java.math.*;


public class Main {

    static class dot implements Comparable<dot>{
        int x;
        int d;
        int index;

        dot(int x, int d, int index){
            this.x = x; //점의 위치
            this.d = d; //시작점, 끝점여부
            this.index = index;//해당 선분의 index
        }

        @Override
        public int compareTo(dot p){ //오름차순정렬, x를 기준으로 정렬하기 위해
            return this.x - p.x;
        }
    }



    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;

        ArrayList<dot> list = new ArrayList<>();

        int start, end;

        for(int i = 0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            start = Integer.parseInt(st.nextToken()); //시작점
            end = Integer.parseInt(st.nextToken()); //끝점

            list.add(new dot(start,+1,i)); //시작점 리스트에 넣기
            list.add(new dot(end,-1,i)); //끝점 리스트에 넣기
        }

        Collections.sort(list);

        HashSet<Integer> s = new HashSet<>();

        int ans = 0;

        for(int i = 0;i<2*n;i++){ //리스트마다 탐색
            int x = list.get(i).x;
            int d = list.get(i).d;
            int index = list.get(i).index;

            if(d == +1){//해당 dot가 시작점이면
                if(s.size() == 0) ans++;//만약 s가 비어있으면 새로운 선분의 시작이므로 답에 1을 추가해준다.
                s.add(index); //현재 탐색중인 선분에 index추가
            }

            else{
                s.remove(index);//끝점을 만나면 현재 탐색중인 선분에 index 삭제
            }
        }

        System.out.println(ans);


    }
}