[2143] 두 배열의 합

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

2143번: 두 배열의 합

누적합과 이분 탐색을 통해 접근하였다.

 

풀이

두 배열의 누적합을 통해 부 배열을 생성, 두 개의 부 배열 중 하나의 부 배열을 오름차순 정렬한 뒤 이분 탐색을 수행, (T - 다른 부배열의 원소) 값을 찾아낸다면 해당 값의 개수만큼 정답을 추가하여 마지막에 출력하면 된다.

 

정답 코드

	import Foundation
	let T = Int(readLine()!)!
	var n = Int(readLine()!)!
	var a = [0]
	for number in readLine()!.split(separator: " ").map({Int($0)!}){
	a.append(a.last!+number)
	}
	var m = Int(readLine()!)!
	var b = [0]
	for number in readLine()!.split(separator: " ").map({Int($0)!}){
	b.append(b.last!+number)
	}
	var tempA = [Int]()
	var tempB = [Int:Int]()
	for i in 0..<n{
	for k in i+1..<n+1{
	tempA.append(a[k]-a[i])
	}
	}
	for i in 0..<m{
	for k in i+1..<m+1{
	let num = b[k]-b[i]
	if tempB[num] == nil{
	tempB[num] = 1
	}else{
	tempB[num]! += 1
	}
	}
	}
	let numbers = tempB.sorted(by: { $0.key < $1.key})
	var ans = 0
	for i in 0..<tempA.count{
	var lead = 0
	var trail = numbers.count-1
	while lead <= trail{
	let mid = (lead+trail)/2
	if numbers[mid].key == T-tempA[i]{
	ans += numbers[mid].value
	break
	}else if numbers[mid].key > T-tempA[i]{
	trail = mid-1
	}else{
	lead = mid+1
	}
	}
	}
	print(ans)

view raw 2143.swift hosted with ❤ by GitHub