[Swift] BOJ 2143 두 배열의 합

BOJ 2143 두 배열의 합

 

 

난이도는 골드3인데 투포인터 + 이진탐색 영역이라고 좀 어려웠다.

삼성 문제풀 때 시뮬레이션 푸는거랑 비슷해서 그냥 정확하게만 풀면 되겠다 싶음.

 

 

 

[알고리즘 접근법] 

1. 부분합(연속적이어야함) 을 A,B 배열을 찾는다.

2. 정렬을 한 후에, 위 아래로 하나씩 보고

 두 수를 더했을 때 찾는 수와 같다면 중복을 체크하여 validCase에 반영한다.

3. 두 수가 더했을 때, 다르다면 그 크기를 체크하여 aIdx or bIdx를 옮긴다.

 

 

샘플 코드

        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)

 

 

 

(참고)

https://woongsios.tistory.com/235

백준 2143 두 배열의 합