[백준] 3273 두 수의 합

문제

https://www.acmicpc.net/problem/3273

 

입력

n = 수열의 길이
arr = 수열
x = 만들어야하는 목표

1 <= n <= 100000
1 <= x <= 2000000
1 <= arr[i] <= 1000000

결과

ans: Int = ai + aj로 x를 만들 수 있는 쌍의 수

해석

1. 각각의 숫자의 개수를 카운팅한다.

2. x = 5 , arr = [2,2,3,3] 일 때 만들 수 있는 경우의 수는  (2,3) ,(3,2) 2개다  하지만 두개를 같게 보기때문에 1개이다.

다시 말하면 식은 다음과 같다 

 

 (ans =  \sum_{i = a_{1}}^{a_{n}} \frac{count(i) + count(j)}{2})

 

나누기 2를 하는 이유는 (2,3) = (3,2)므로 

 

 

코드

import Foundation

let n = Int(readLine()!)!

let arr = readLine()!.split{$0 == " "}.map{Int($0)!}.sorted()
let x = Int(readLine()!)!

var ans: Int = 0

var left: Int = 0
var right: Int = n-1

let max = 1000000

var count: [Int] = [Int](repeating: 0, count: max+1)

for num in arr {
    count[num] += 1
}

for n1 in arr {
    if n1 >= x { // x를 넘거나 같으면 쌍을 만들 수 없음
        break
    }
    
    let n2 = x-n1
    
    if n1 > max || n2 > max { // 범위를 벗어남
        continue
    }
    
    
    ans += (count[n1] * count[n2])
    
}

print(ans/2)