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
'알고리즘 문제 풀이' 카테고리의 다른 글
[Swift] BOJ 1647 도시 분할 계획 (0) | 2022.05.16 |
---|---|
[Swift] BOJ 1197 최소 스패닝 트리 (0) | 2022.05.16 |
[Swift] BOJ 2352 반도체 설계 (0) | 2022.05.12 |
[Swift] BOJ 2805 나무 자르기 (0) | 2022.05.12 |
[Swift] BOJ 1920 수 찾기 (0) | 2022.05.12 |