백준 2143 두 배열의 합

출처: www.acmicpc.net/problem/2143

분류: 이분 탐색, 투 포인터

---

접근방식

합이 0인 네 정수 문제와 비슷했던 문제였습니다. 

주어진 각 배열에서 나올 수 있는 부분합을 모두 구해준 뒤 정렬해서 

투 포인터로 해결했습니다.

마찬가지로 T인 케이스를 찾았을 때 중복인 수의 개수를 세서 쌍을 찾아줘야 합니다 :)

 

해결방법

let t = Int(readLine()!)!
let n = Int(readLine()!)!
let a = readLine()!.split(separator: " ").map { Int(String($0))! }
let m = Int(readLine()!)!
let b = readLine()!.split(separator: " ").map { Int(String($0))! }

var aSum = [Int]()
var bSum = [Int]()

for i in 0..<a.count {
    var tempSum = a[i]
    aSum.append(tempSum)
    for j in i+1..<a.count {
        tempSum += a[j]
        aSum.append(tempSum)
    }
}

for i in 0..<b.count {
    var tempSum = b[i]
    bSum.append(tempSum)
    for j in i+1..<b.count {
        tempSum += b[j]
        bSum.append(tempSum)
    }
}

aSum.sort(by: <)
bSum.sort(by: <)

var aIdx = 0
var bIdx = bSum.count-1

var validCase = 0
while aIdx < aSum.count, bIdx >= 0 {
    let sum = aSum[aIdx] + bSum[bIdx]
    if sum == t {
        let validA = aSum[aIdx]
        let validB = bSum[bIdx]
        var duplicatedA = 0
        var duplicatedB = 0
        
        while aIdx < aSum.count, aSum[aIdx] == validA {
            duplicatedA += 1
            aIdx += 1
        }
        
        while bIdx >= 0, bSum[bIdx] == validB {
            duplicatedB += 1
            bIdx -= 1
        }
        
        validCase += duplicatedA * duplicatedB
    } else if sum < t {
        aIdx += 1
    } else {
        bIdx -= 1
    }
}

print(validCase)

 

배운점

유사한 문제를 풀었는데도 처음에 중복을 제대로 계산해주지 못했고,

실수를 많이해서 생각보다 시간이 좀 걸렸었다.