백준 7453 합이 0인 네 정수

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

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

---

접근방식

4개의 배열이 주어지고 각 원소의 합이 0이되는 쌍이 몇 개인지 찾는 문제입니다.

이 문제의 첫 번째 아이디어는 4개의 배열을 각각 생각하려고 하면 힘드니 2개씩 묶어서 합쳐주는 것입니다.

a b 의 합이 될 수 있는 모든 경우를 담은 배열 ab,
c d 의 합이 될 수 있는 모든 경우를 담은 배열 cd

를 만들고 둘 모두 오름차순으로 정렬해줍니다.

 

다음으로 ab는 작은 수부터, cd는 큰 수부터 포인터를 움직여 0이 되는 경우를 찾는 것입니다.

ab, cd 원소의 합이 0보다 작으면 low를 증가시키고 0보다 크면 high를 줄여줍니다.

sum이 0일 때 주의해야할 건 중복을 찾아서 쌍을 계산해줘야 합니다.

ab = [ -3, -3, -3 ]

cd = [ 3, 3, 3 ]

이렇게 둘 모두 중복이라면, 0이 될 수 있는 순서 쌍은 3 x 3으로 9개가 됩니다. 

 

해결방법

var a = [Int]()
var b = [Int]()
var c = [Int]()
var d = [Int]()
let n = Int(readLine()!)!
for _ in 0..<n {
    let arr = readLine()!.split(separator: " ").map { Int(String($0))! }
    a.append(arr[0])
    b.append(arr[1])
    c.append(arr[2])
    d.append(arr[3])
}

var ab = [Int]()
var cd = [Int]()

for i in 0..<n {
    for j in 0..<n {
        ab.append(a[i] + b[j])
        cd.append(c[i] + d[j])
    }
}
ab.sort(by: <)
cd.sort(by: <)

var low = 0
var high = cd.count-1

var zeroCase = 0
while low < ab.count, high >= 0 {
    let sum = ab[low] + cd[high]
    var abDuplicate = 0
    var cdDuplicate = 0
    if sum == 0 {
        let abSum = ab[low]
        let cdSum = cd[high]
        while low < ab.count, ab[low] == abSum {
            abDuplicate += 1
            low += 1
        }
        
        while high >= 0, cd[high] == cdSum {
            cdDuplicate += 1
            high -= 1
        }
        
        zeroCase += abDuplicate * cdDuplicate
    } else if sum < 0 {
        low += 1
    } else {
        high -= 1
    }
}

print(zeroCase)

 

 

배운점

이 문제도 너무 어려웠다.. ㅠㅠ 요즘 이분 탐색을 계속 풀고 있는데 어찌도 이리 다양한지... 연습만이 살길