알고리즘 문제 풀이

[Swift] BOJ 2143 두 배열의 합

lgvv 2022. 5. 13. 00:39

BOJ 2143 두 배열의 합

 

✅ 두 배열의 합

난이도는 골드3.. 근데 투 포인터 + 이진탐색? 영역이라서 극한으로 어려웠다.

이 문제를 풀기 전에 

2022.05.12 - [코딩테스트] - [Swift] BOJ 7453 합이 0인 네 정수

 

위 문제 푸는데 엄청나게 시간 많이 들었는데 ㅠ

투 포인터라니.. 이런 흐름을 가져가는 문제도 있다는 것을 알아두면 코딩 테스트에서 구현할 수 있겠지.

 

[알고리즘 접근법] 

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 두 배열의 합

출처: www.acmicpc.net/problem/2143 분류: 이분 탐색, 투 포인터 접근방식 합이 0인 네 정수 문제와 비슷했던 문제였습니다. 주어진 각 배열에서 나올 수 있는 부분합을 모두 구해준 뒤 정렬해서 투 포인

woongsios.tistory.com