[8983] 사냥꾼

https://www.acmicpc.net/problem/8983

8983번: 사냥꾼

이분탐색으로 접근했다.

---

풀이 방법

주어지는 사대의 위치를 오름차순으로 정렬한다.

이후 주어진 각 동물의 좌표를 기준으로 사대의 위치 0부터 M-1까지 이분탐색을 통해 사격 거리 L에 포함되는지를 확인하였다.

 

이때 사격거리 L에 포함되지 않는다면 동물의 위치가 비교한 사대보다 왼쪽이라면 즉 (동물의 x축 좌표 < 사대의 x축 좌표)이라면, 현재 사대보다 더 왼쪽에 위치한 사대를 탐색하면 되고, 그 반대라면 보다 오른쪽에 위치한 사대를 탐색하면 된다.

 

해당 방법으로 접근한다면 O(100,000 * log100,000) 즉 O(500,000)에 탐색이 가능하다.

---

정답 코드

	import Foundation
	let (M,N,L) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1], $0[2])}[0]
	var animal = [(a:Int, b:Int)]()
	var position = readLine()!.split(separator: " ").map({Int($0)!}).sorted(by: <)
	var ans = 0
	for _ in 0..<N{
	let (a,b) = [readLine()!.split(separator: " ").map{Int($0)!}].map{($0[0], $0[1])}[0]
	if b<=L { animal.append((a,b)) }
	}
	for target in animal{
	var lo = 0
	var hi = M-1
	while lo <= hi{
	let mid = (lo+hi)/2
	if abs(target.a-position[mid])+target.b <= L{
	ans += 1
	break
	}else if target.a < position[mid]{
	hi = mid-1
	}else{
	lo = mid+1
	}
	}
	}
	print(ans)

view raw 8983.swift hosted with ❤ by GitHub