[Swift] BOJ 7453 합이 0인 네 정수

BOJ 7453 합이 0인 네 정수

 

 

이진탐색 개념은 간단한데, 생각보다 어려웠다.

 

 

알고리즘 접근법 

이 문제의 경우에는 시간 제한이 있기 때문에, 다중 for문과 contains로는 해결할 수 없다.

 

1. input과정에서 column을 4개를 만들어서 따로 받는다.

2. col 1,2 그리고 col3,4를 for문으로 더해서 나올 수 있는 케이스를 구한다. (sumAB, sumCD)

3. sumAB와 sumCD를 정렬한다.(나는 오름차순으로 정렬)

4. (핵심)

 sumAB는 앞 부분부터 sumCD는 뒤 부분부터 순회하면서 값을 비교

 -> 왜냐하면 가장 작은 값과 가장 큰 값의 합이어야 0이 나올 수 있기 때문

 

 

1. sumAB의 값과 sumCD에서 참조한 값의 합이 0일 경우

 

이 경우에는 result를 하나 올려줍니다. 근데 여기서 유의할 점이 있습니다.

sumAB = [-3, -3, -3, 2, 5 ,7]

sumCD = [-5,-3, 1, 2, 3, 3] 

이런식으로 중복이 있는 경우입니다.

 

이 경우에는 sumAB에서 -3의 갯수만큼 sumCD에서 3의 갯수만큼을 찾습니다.

그리고 각각에서 나온 갯수를 곱한 만큼 경우의 수가 만들어지므로 이 값을 result에 반영합니다.

 

 

2. sumAB의 값과 sumCD에서 참조한 값의 합이 0보다 작은 경우

 

이 경우에는 left의 값을 1증가시켜 줍니다.

너무 큰값이 들어있거나 혹은, 너무 작은 값이 들어있기 때문인데, 이건 자유롭게 설정하면 됩니다.

 

 

3. sumAB의 값과 sumCD에서 참조한 값의 합이 0보다 큰 경우

 

위와 동일한 논리에서 right의 값을 1 감소시켜 줍니다.

 

 

        let n = Int(readLine()!)!
        
        var a = [Int64]()
        var b = [Int64]()
        var c = [Int64]()
        var d = [Int64]()
        
        for _ in 0..<n {
            let temp = readLine()!.split(separator: " ").map { Int64(String($0))! }
            a.append(temp[0])
            b.append(temp[1])
            c.append(temp[2])
            d.append(temp[3])
        }
        
        var sumAB = [Int64]()
        var sumCD = [Int64]()
        
        for i in 0..<n {
            for j in 0..<n {
                sumAB.append(a[i] + b[j])
                sumCD.append(c[i] + d[j])
            }
        }
        
        sumAB.sort()
        sumCD.sort()
        
        var result: Int64 = 0
        var left = 0
        var right = sumAB.count - 1
        
        while left < sumAB.count && right >= 0 {
            let sum = sumAB[left] + sumCD[right]
            
            if sum == 0 { // 같을 경우
                // 중복이 몇개 있는지 체크합니다.
                var xCount: Int64 = 0
                var yCount: Int64 = 0
                let x = sumAB[left], y = sumCD[right]
                
                while sumCD[right] == y {
                    yCount += 1
                    right -= 1
                    if right == -1 { break } // right가 인덱스의 범위를 벗어남
                }
                
                while sumAB[left] == x {
                    xCount += 1
                    left += 1
                    if left == sumAB.count { break } // left가 인덱스의 범위를 벗어남
                }
                
                result += xCount * yCount
                
            } else if sum < 0 {
                left += 1
            } else {
                right -= 1
            }
        }
        
        print(result)