문제
일차원 좌표상의 점 N개와 선분 M개가 주어진다. 이때, 각각의 선분 위에 입력으로 주어진 점이 몇 개 있는지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 끝점이 주어진다. 입력으로 주어지는 모든 좌표는 1,000,000,000보다 작거나 같은 자연수이다.
틀린 풀이
# 선분 위의 점
# 복습 횟수:0, 00:30:00, 복습필요:O
import sys
si = sys.stdin.readline
N, M = map(int, si().split())
point_list = list(map(int, si().split()))
line_list = []
for i in range(M):
line = list(map(int, si().split()))
line_list.append(line)
def binary(start, end, target):
while start <= end:
mid = (start + end) // 2
if mid == target:
return 1
if mid > target:
end = mid - 1
else:
start = mid + 1
return 0
for start, end in line_list:
cnt = 0
for point in point_list:
flag = binary(start, end, point)
if flag:
cnt += 1
print(cnt)
이분 탐색을 사용하였지만
for 문이 2개로 O(N^2 * logN)의 시간 복잡도가 걸려 시간초과가 난 풀이이다.
정답 풀이
# 선분 위의 점
# 복습 횟수:0, 01:45:00, 복습필요:O
import sys
si = sys.stdin.readline
N, M = map(int, si().split())
point_list = list(map(int, si().split()))
point_list.sort()
line_list = []
for i in range(M):
line = list(map(int, si().split()))
line_list.append(line)
def binary_min(start, end, target):
while start <= end:
idx = (start + end) // 2
mid = point_list[idx]
if target > mid:
start = idx + 1
else:
end = idx - 1
return end + 1
def binary_max(start, end, target):
while start <= end:
idx = (start + end) // 2
mid = point_list[idx]
if target >= mid:
start = idx + 1
else:
end = idx - 1
return end
# 최소값의 index와 최대값의 index를 비교하는 방법으로 문제를 해결하기
for least, largest in line_list:
start = 0 # index
end = len(point_list) - 1 # index
mini = binary_min(start, end, least)
maxi = binary_max(start, end, largest)
print(maxi - mini + 1)
아이디어
1. 최소값의 index와 최대값의 index를 비교해 "개수"만 구하는 방식
2. 최소 값과 최대값의 index를 체크하기 위해 이분탐색을 두번 하므로
for 문 하나 + 이분탐색 = 시간복잡도 O(NlogN)이 되어 시간초과 문제를 해결할 수 있다.
'Koala - 9기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/python] 10816번 숫자 카드 2 (0) | 2023.01.29 |
---|---|
[백준/C++] 2110번 공유기 설치 (0) | 2023.01.28 |
[백준 / Python] 15038번 Lounge Lizards (0) | 2023.01.25 |
[백준/c++] 3027번 입국심사 (Binary Search) (0) | 2023.01.25 |
[백준/python] 1806번 부분합 (0) | 2023.01.22 |