백준 1689 겹치는 선분 Cpp, Java

작성일 | In |

Problem : 겹치는 선분

유형 : 라인 스위핑

문제해석

  • 겹치는 선분이 최대 몇개인지를 확인한다.
  • 선분이 한개만 있으면 1개가 겹쳐있다고 생각한다.

해결전략

  • 입력이 100만이므로, 라인스위핑을 통해서 O(N)으로 문제를 해결한다.
  • 선분은 두개의 점으로 이루어져있으니, 시작점 빠른순으로 정렬한다. 만약 시작점과 끝점의 위치가 같다면 끝점을 먼저 계산한다. (끝점은 겹치지 않으므로)

구현

  • (시작점, 1) (끝점, 0) 순으로 정렬한다. 끝점이 0인이유는 위치가 같은경우 끝점이 먼저 계산되어야 하기때문이다.
  • 시작점을 만남 == 현재 구간에서 선분이 추가됨 이므로 카운트업을하고, 겹치는 구간 최댓값을 갱신한다.
  • 끝점을 만남 == 해당 구간에서 겹치는 선분이 끝남 이므로 현재까지 겹쳐있는 개수를 감소시킨다.

주의할점

  • 선분이 한개만 있으면 1개가 겹쳐있다고 생각한다.
1
2
1
1 2
  • 위의 경우 답은 1이다.

코드

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

const int START_TYPE = 1;
const int END_TYPE = 0;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin >> t;

  vector<pair<int, int>> spots;

  int start, end;
  while (t--) {
    cin >> start >> end;
    spots.push_back({start, START_TYPE});
    spots.push_back({end, END_TYPE});
  }

  sort(spots.begin(), spots.end());

  int answer = 0;
  int conflictCount = 0;
  for (auto spot : spots) {
    if (spot.second == START_TYPE) {
      conflictCount++;
      answer = max(answer, conflictCount);
    } else {
      conflictCount--;
    }
  }

  cout << answer << "\n";
  return 0;
}

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static final int START_TYPE = 1;
    private static StringTokenizer st;

    public static void main(String[] args) throws IOException {
        int lineCount = Integer.parseInt(br.readLine());
        List<Spot> spots = new ArrayList<>();
        for (int i = 0; i < lineCount; ++i) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            spots.add(new Spot(start, 1));
            spots.add(new Spot(end, 0));
        }
        Collections.sort(spots);

        int answer = 0;
        int conflictCount = 0;
        for (Spot spot : spots) {
            if (spot.type == START_TYPE) {
                conflictCount++;
                answer = Math.max(answer, conflictCount);
            } else {
                conflictCount--;
            }
        }

        System.out.println(answer);
    }
}

class Spot implements Comparable<Spot> {
    int point;
    int type;

    public Spot(final int point, final int type) {
        this.point = point;
        this.type = type;
    }

    @Override
    public int compareTo(final Spot o) {
        if (point == o.point) {
            return Integer.compare(type, o.type);
        }
        return Integer.compare(point, o.point);
    }
}