[파이썬/Python] 백준 11663번: 선분 위의 점

숨·2024년 9월 22일

알고리즘 문제 풀이

목록 보기

82/105

📌 문제 : 백준 11663번

📌 문제 탐색하기

N : 점의 개수 $(1 ≤ N ≤ 100,000)$
M : 선분의 개수 $(1 ≤ M ≤ 100,000)$
locations : N개의 점 좌표 $(1 ≤ locations ≤ 1,000,000,000)$

N개의 점 좌표와 M개의 선분의 시작점-끝점 좌표를 입력받아 N개의 점 좌표 중 각 선분에 있는 좌표의 수를 M번 구하는 문제이다.

문제 풀이

⭐️ 좌표 입력 조건

좌표는 같은 좌표 ❌ → 서로 다른 좌표

모든 좌표의 크기 범위가 매우 큼을 주의해야 한다.

M개의 선분에 접근해서 선분의 범위 내에서 시작점에 가까운 점과 끝점에 가까운 점을 찾는다.
→ 각 점에 이분탐색을 진행한다.

입력 받은 점의 좌표를 오름차순 정렬 필요❗️
시작점에 가까운 점 찾는 이분탐색, 끝점에 가까운 점 찾는 이분탐색 2가지를 구현
- 시작점에 가까운 점 찾는 이분탐색
  - 시작 0, 끝 N - 1 (인덱스로 접근할 것이므로)
    - 중앙값이 시작점보다 작으면 시작 인덱스 늘려보기
    - 중앙값이 시작점보다 크면 끝 인덱스 줄여보기
- 끝점에 가까운 점 찾는 이분탐색
  - 시작 0, 끝 N - 1 (인덱스로 접근할 것이므로)
    - 중앙값이 끝점보다 작거나 같으면 시작 인덱스 늘려보기
    - 중앙값이 끝점보다 크면 끝 인덱스 줄여보기
- 최종) 시작 인덱스에 원하는 값이 담기게 된다.

그 두 점 사이의 점 개수를 세서 출력하면 된다.
→ 찾은 점들의 인덱스 차를 구한다면 for문을 이용해서 하나씩 세지 않아도 될 것 같다!

가능한 시간복잡도

점 좌표 정렬 → $O(N log N)$
2개의 이분탐색을 M번 반복 → $O(M log N)$

최종 시간복잡도
$O(N log N + M log N)$ 가 되어 최악의 경우 $O(200,000 * log (100,000))$ 로 1초 내에 연산이 가능하다.

알고리즘 선택

M개의 선분을 2개의 이분탐색으로 상한, 하한을 찾아 그 사이 점의 좌표 수 구하기

📌 코드 설계하기

선분의 시작점에 가까운 점의 인덱스 찾는 이분탐색 구현
선분의 끝점에 가까운 점의 인덱스 찾는 이분탐색 구현
필요한 입력 받기
점 좌표 정렬
각 선분에 대해 이분탐색 수행
결과 출력

📌 시도 회차 수정 사항

1회차

def find_end(locations, target):
    start, end = 0, N - 1
    while start <= end:
        mid = (start + end) // 2
        if locations[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start

예제 입력1에 대한 답이 2 2 3 2 0으로 틀리게 나왔다.
시작 인덱스 찾듯이 if문의 조건을 작성하면 된다고 생각했는데 끝 인덱스는 끝점보다 작거나 같을 때를 찾아야 하기 때문에 조건에 <이 아닌 <=를 사용해야 했다.

📌 정답 코드

import sys

input = sys.stdin.readline


# 시작점과 가까운 점을 찾기
def find_start(locations, target):
    start, end = 0, N - 1
    while start <= end:
        mid = (start + end) // 2
        if locations[mid] < target:
            start = mid + 1
        else:
            end = mid - 1
    return start


# 끝점과 가까운 점을 찾기
def find_end(locations, target):
    start, end = 0, N - 1
    while start <= end:
        mid = (start + end) // 2
        if locations[mid] <= target:
            start = mid + 1
        else:
            end = mid - 1
    return start


# N, M 입력
N, M = map(int, input().split())

# N개의 좌표 입력
locations = list(map(int, input().split()))

# M개의 선분의 시작점 끝점 입력
lines = [list(map(int, input().split())) for _ in range(M)]

# 좌표 정렬
locations.sort()

# 각 선분에 대해 계산
for line in lines:
    start, end = line
    start_idx = find_start(locations, start)
    end_idx = find_end(locations, end)

    # 결과 출력
    print(end_idx - start_idx)