[코드트리] - Sweeping

문제 - 가장 많이 겹치는 구간 (기본문제)

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-section-with-maximum-overlap/description

가장 많이 겹치는 구간 설명 | 코드트리

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

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    public static void main(String[] args) throws IOException{
        int N = read();
        int[][] pos = new int[2*N][2];

        for(int i = 0; i<N; i++){
            int a = read();
            int b = read();

            pos[2*i] = new int[]{a, 1};
            pos[2*i+1] = new int[]{b, -1};
        }

        Arrays.sort(pos, Comparator.comparingInt(a->a[0]));
        int cnt = 0;
        int ans = 0;
        for(int i = 0; i<2*N; i++){
            cnt += pos[i][1];
            ans = Math.max(ans, cnt);
        }
        System.out.print(ans);
    }
}

풀이 설명

선분의 양 끝 점의 위치가 차례로 주어졌을 때 가장 많이 중복되는 곳의 선분 갯수를 구하는 문제이다. 

이벤트 스위핑 기법으로 풀이한다. 

먼저 입력을 받을 때 데이터가 아닌 이벤트 기준으로 입력을 받는다.

-> 이벤트란 선분이 시작됨. 선분이 끝남 이거 2개니까 pos는 2*N의 크기를 가진다.

 

선분이 시작될 때 +1, 선분이 끝날때 -1로 입력을 받고

여기서는 시작과 끝이 닿았을 때 중복이 아닌 문제이므로 그냥 a,b 증감없이 받는다.

그리고 이벤트 발생 지점을 기준으로 오름차순으로 이벤트 배열을 정렬하고 

차례로 보며 이벤트 값을 cnt에 더해준다. 

-> 이때의 순간 최댓값을 구하면 정답

---

문제 - 서로 다른 구간 갯수

https://www.codetree.ai/ko/trails/complete/curated-cards/intro-number-of-distinct-segments/description

서로 다른 구간의 수 설명 | 코드트리

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

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    public static void main(String[] args) throws IOException{
        int N = read();
        int[][] pos = new int[2*N][2];
        for(int i = 0; i<N; i++){
            int a = read();
            int b = read();
            pos[2*i] = new int[]{a,1};
            pos[2*i+1] = new int[]{b,-1};
        }

        Arrays.sort(pos, Comparator.comparingInt(a->a[0]));
        int cnt = 0;
        int prev = 0;
        int ans = 0;
        for(int i = 0; i<2*N; i++){
            cnt += pos[i][1];
            if(prev == 0 && cnt == 1){
                ans++;
            }
            prev = cnt;
        }
        System.out.print(ans);
    }
}

풀이 설명

이벤트 단위로 입력을 받고 정점과 정점의 끝이 포함으로 세지 않으므로 그냥 a,b로 받음.

선분들이 주어지고 겹친 선분끼리는 합친다고 했을때 이 연산을 끝까지 반복한 결과의 선분 덩어리의 총 갯수 구하기

-> 이벤트 델타값 기준으로 0에서 1로 변화할때 한 덩어리의 시작이므로 이거 갯수 세 주기

---

문제 - 겹치는 선분들

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-overlapping-lines/description

겹치는 선분들 설명 | 코드트리

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

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    static char rc() throws IOException{
        sst.nextToken();
        return (char) sst.sval.charAt(0);
    }

    public static void main(String[] args) throws IOException{
        int N = read();
        int K = read();

        int[][] pos = new int[2*N][2];

        int prev = 0;
        for(int i = 0; i<N; i++){
            int a = read();
            char cmd = rc();
            if(cmd == 'R'){
                pos[2*i] = new int[]{prev, 1};
                pos[2*i+1] = new int[]{prev+a, -1};
                prev += a;
            }
            else{
                pos[2*i] = new int[]{prev-a, 1};
                pos[2*i+1] = new int[]{prev, -1};
                prev -= a;
            }
        }

        Arrays.sort(pos, Comparator.comparingInt(a->a[0]));
        int cnt = 0;
        long sum = 0;

        // 길이는 항상 현재 이벤트 ~ 다음 이벤트 에서 발생함
        for(int i = 0; i<2*N-1; i++){
            cnt += pos[i][1];
            int len = pos[i+1][0] - pos[i][0];
            if(cnt >= K){
                sum += len;
            }  
        }
        System.out.print(sum);
    }
}

풀이 설명

문제 입력에서 num, L or R로 주어지는데 이는 맨 처음은 원점에서 시작해서 num 만큼 left or Right로 선을 그리고

그다음 마지막 위치에서 시작해서 또 num 만큼 방향대로 그리는 것임

-> L = prev-a ~ prev, R = prev ~ prev+a를 기준으로 이벤트 델타값을 입력받음

 

이벤트 발생 시점을 기준으로 오름차순 정렬하고 

K개 이상의 선분이 겹치는 곳의 길이를 구하는 문제인데

길이는 항상 다음 이벤트 시점이 존재할 때 다음 이벤트 시점 - 현재 이벤트 시점으로 구해짐

그러면 겹쳐진 갯수는 cnt에 이벤트 델타값을 누적해서 구하고 길이 구한것을 cnt가 K 이상일때 누적하면 답

---

문제 - 합쳐진 덩어리의 구간 합

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-sum-of-interval-sizes/description

구간 크기의 합 설명 | 코드트리

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

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    public static void main(String[] args) throws IOException{
        int N = read();
        int[][] pos = new int[2*N][2];
        for(int i = 0; i<N; i++){
            int a = read();
            int b = read();
            pos[2*i] = new int[]{a,1};
            pos[2*i+1] = new int[]{b,-1};
        }

        Arrays.sort(pos, Comparator.comparingInt(a->a[0]));
        int cnt = 0;
        int prev = 0;
        int s = 0;
        long ans = 0;
        for(int i = 0; i<2*N; i++){
            cnt += pos[i][1];
            if(prev == 0 && cnt == 1)
                s = pos[i][0];
            if(prev == 1 && cnt == 0){
                ans += pos[i][0] - s;
            }
            prev = cnt;
        }
        System.out.print(ans);
    }
}

풀이 설명

모든 겹쳐진 선분을 합하는 연산을 끝까지 진행했을때 한 덩어리의 크기들의 합을 구하기

한 덩어리의 시작 부분은 cnt의 변화가 0->1 일때 시작이고 1->0일때 끝임

-> 시작 부분에서 현재 이벤트의 발생 지점이 start이고 

끝 부분에서 현재 이벤트의 발생 지점이 end이므로 pos[i][0] - s를 누적하면 답임.

---

문제 - 호텔 방 관리(PriorityQueue)

https://www.codetree.ai/ko/trails/complete/curated-cards/test-reserve-hotel/description

호텔 예약 설명 | 코드트리

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

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    public static void main(String[] args) throws IOException{
        int N = read();
        // 이벤트 시각, 델타값, 사람 번호
        int[][] E = new int[2*N][3];
        for(int i = 0; i<N; i++){
            int a = read();
            int b = read();

            E[2*i] = new int[]{a, 1, i+1};
            E[2*i+1] = new int[]{b, -1, i+1};
        }

        Arrays.sort(E, (a,b)->{
            if(a[0] != b[0])
                return a[0] - b[0];
            return b[1] - a[1];
        });

        int nextRoom = 0;
        // 비어있는 방 번호
        PriorityQueue<Integer> q =new PriorityQueue<>();
        // i번 사람이 val 방 쓰는중
        int[] using = new int[N+1];
        Set<Integer> ans = new HashSet<>();

        for(int i= 0; i<2*N; i++){
            // 입실 발생
            if(E[i][1] == 1){
                int nRoom = 0;
                if(q.isEmpty()){
                    nRoom = nextRoom++;
                }
                else{
                    nRoom = q.poll();
                }
                // 사람을 방에 배정
                using[E[i][2]] = nRoom;
                ans.add(nRoom);
            }
            // 퇴실 발생
            else{
                q.add(using[E[i][2]]);
            }
        }
        System.out.print(ans.size());
    }
}

사고의 흐름

N명의 사람의 입실과 퇴실 시각 기록이 주어질 때 이 사람들을 모두 한 호텔에 수용하기 위한 최소 호텔 방 수는 몇일지 계산

이벤트 단위 배열로 나누어 [ 이벤트 발생 시각, 델타 값(입실, 퇴실 구분용), 사람 번호 ] 로 저장함.

-> 발생 시각 오름차순, 델타 값 내림차순으로 정렬함

-> 그래야 같은 날 입실 이벤트를 먼저 처리하게 됨.

 

풀이

사용자가 쓰고 남은 여유 방 중 방 번호가 가장 작은게 먼저 사용될 방 번호를 관리하는 우선순위 큐 하나를 두고,

i번 사람이 val 값 방 번호를 현재 점유 중임을 나타내는 N+1 짜리 배열과

중복되지 않는 방번호 Set(answer)를 정의함

 

1) 입실 이벤트 발생

-> 현재 잔여 빈방이 없음 : nextRoom이 배정될 방이고 이후 nextRoom += 1

-> 현재 잔여 빈방이 있음 : 우선순위 큐에서 하나 꺼내서 배정될 방으로 선정함

using[ 현재 사람 번호 ] = 배정될 방 번호

 

2) 퇴실 이벤트 발생

-> 잔여 빈 방이 발생하므로 우선순위 큐에 using [ 현재 사람 번호 ] 의 값을 넣는다.

 

1, 2번을 모든 이벤트 단위 시각에 대해서 반복하고

using 배열에 방 번호가 갱신될 때마다 Set에 넣어 중복되지 않게 어떤 방들이 사용되었는지 기록하면

입/퇴실 기록에 따른 모든 사용자를 수용하기 위한 최소 호텔 방 수는 Set.size() 이다.

---

문제 - 선분 합 최대화 (다시 보기, 집합 관리)

https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-remove-the-line-segment-for-the-maximum-length/description

최대 길이를 위해 선분 제거하기 설명 | 코드트리

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

    static int read() throws IOException{
        sst.nextToken();
        return (int) sst.nval;
    }

    public static void main(String[] args) throws IOException{
        int N = read();
        // etime, delta, idx
        int[][] E = new int[2*N][3];
        for(int i = 0; i<N; i++){
            int a = read();
            int b = read();

            E[2*i] = new int[]{a,1,i};
            E[2*i+1] = new int[]{b,-1,i};
        }

        Arrays.sort(E, (a,b)->{
            if(a[0]!=b[0])
                return a[0] - b[0];
            return b[1] - a[1];
        });

        int cnt = 0;
        int[] lens = new int[N];
        int total = 0;

        // cnt = 1 활성화 된 선분 자기 하나
        // cnt > 0 선분 활성화되어 있음 len 전부 더하면 합집합 길이 됨.
        // -> cnt로만으로는 어떤 선분에 이어야할지 불명확함

        TreeSet<Integer> ts = new TreeSet<>();
        for(int i = 0; i<2*N-1; i++){
            int len = E[i+1][0] - E[i][0];
            cnt += E[i][1];

            // 시작이벤트는 활성화된 선분으로 등록
            if(E[i][1] == 1)
                ts.add(E[i][2]);
            // 끝이벤트는 활성화된 선분에서 빼기
            else
                ts.remove(E[i][2]);

            if(cnt != 0)
                total += len;
            if(cnt == 1){
                int idx = ts.iterator().next();
                lens[idx] += len;
            }
                
        }

        int ans = 0;
        for(int i = 0; i<N; i++){
            ans = Math.max(ans, total - lens[i]);
        }
        System.out.print(ans);
    }
}

사고의 흐름 및 풀이

문제 조건처럼 하나의 선분만 제외해서 전체 선분의 길이 합집합을 가장 크게 하려면 그 선분만 덮고 있었던 길이를 빼면 된다.

그렇다면 이벤트 스위핑에서 cnt는 현재 활성화된 선분의 수를 의미하므로

cnt가 1일때 다음 이벤트 - 지금 이벤트 를 더하면 되는데

여기서 하나의 스위핑에서 여러개의 하나만 살아남은 선분이 있을 수 있다. 

 

-> TreeSet을 이용해서 cnt가 1일때 iterator().next()로 그 선분의 idx를 찾아 lens 배열을 갱신한다.

TreeSet은 현재 활성화된 선분이므로 시작 이벤트에서 add하고 끝 이벤트에서 remove한다.

 

전체 합집합의 경우 선분이 1개 이상 활성화 되어 있을때 len을 합산하면 중복 없이 전체 선분이 덮는 길이를 구할 수 있다.

---