[7453] 합이 0인 네 정수

toru93·2022년 9월 23일
0
[2143] 두 배열의 합과 비슷한 문제
let n = Int(readLine()!)!
var arr = [[Int]]()
var sumL = [Int]()
var sumR = [Int]()
var s = 0
var e = 0
var cnt = 0

for _ in 0..<n {
    arr.append(readLine()!.split(separator: " ").map{Int(String($0))!})
}

for i in 0..<n {        // 순열
    for j in 0..<n {
        sumL.append(arr[i][0] + arr[j][1])
        sumR.append(arr[i][2] + arr[j][3])
    }
}					   
sumL.sort()             // 정렬
sumR.sort()            	// 1. 정렬돼 있어야 투포인터 가능.
e = sumL.count-1		// 2. 연속되는 원소를 구할 수 있다.

while s < sumL.count, 0 <= e {
    let sum = sumL[s] + sumR[e]
    if sum == 0 {
        var cntL = 0
        var cntR = 0
        let valueL = sumL[s]
        let valueR = sumR[e]
        
        while s < sumL.count, sumL[s] == valueL {   // 연속되는 원소 카운트
            s += 1
            cntL += 1
        }
        while 0 <= e, sumR[e] == valueR {
            e -= 1
            cntR += 1
        }
        cnt += cntL * cntR
    }
    else if sum < 0 {
        s += 1
    }else {
        e -= 1
    }
}
print(cnt)
profile
iOS

0개의 댓글