[Swift][브루트포스] 백준 2143번 (두 배열의 합)

요구능력

해시, 브루트포스

 

문제풀이

부분합 문제는 연속되서 브루트포스를 하게되면 n^2의 시간복잡도를 가지게되고,

연속되지않게 부분수열과 같은 문제가나오면 2^n의 시간복잡도를 가지게 된다.

 

이 문제는 연속되기 때문에 편하게 푸려면 브루트포스를 생각해봐야한다.

n과 m이 1000이하이므로 n^2을 시도해봐도 괜찮을 것같다.

 

부분합을 구해주면서 dictionary에 해당 부분합이 나오는 개수를 저장을 해준다.

반으로 쪼개지는 않았지만, 이것도 중간에서 만나기 개념이 살짝 사용되는거같은데..?(아닌가)

 

그리고 나머지부분합을 구하면서 해시를 이용하여 목표값을 달성하는 개수를 result에 누적해준다.

 

후기

이전 문제랑 비슷하게 풀리는데..

이건 연속된 배열이고, 이전 문제는 연속되지 않기때문에 2^n

 

코드

let t = Int(String(readLine()!))!
var n = Int(String(readLine()!))!
let nArr = readLine()!.split(separator: " ").map{Int(String($0))!}
var m = Int(String(readLine()!))!
let mArr = readLine()!.split(separator: " ").map{Int(String($0))!}

var dict = [Int: Int]()

for i in 0..<n{
    for j in i..<n{
        let sum = nArr[i...j].reduce(0, +)
        if dict[sum] != nil{
            dict[sum]! += 1
        }else{
            dict[sum] = 1
        }
    }
}
var result = 0
for i in 0..<m{
    for j in i..<m{
        let sum = mArr[i...j].reduce(0, +)
        if dict[t - sum] != nil{
            result += dict[t - sum]!
        }
        
    }
}
print(result)