[백준] 3273 - 두 수의 합

Ai 번째 숫자와 합하여 X 가 되는 쌍을 찾는 문제이다.
나의 경우 이분탐색을 활용하여 풀었지만, 투포인터 알고리즘을 활용하면 더 빠르게 탐색이 가능하다고 한다.

풀이 1. 이분 탐색 (내 방식)

/*
* Array(n) 을 설정
* var limitIndex = Arr.binarySearch(x)
* if(limitIndex < 0){
*   limitIndex = -(limitIndex + 1)
* }
*
* */
fun `3273 - 두 수의 합`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val token = java.util.StringTokenizer(br.readLine())
    val arr = IntArray(n){ token.nextToken().toInt() }
    val x = br.readLine().toInt()
    var count = 0

    arr.sort()

    for(i in 0 until n){
        val searchIndex = arr.binarySearch(x - arr[i])

        if(searchIndex > i){
            count++
        } else if(searchIndex >= 0) break
    }

    bw.write(count.toString())
    bw.flush()
    bw.close()
    br.close()
}

이분탐색, 이항을 통해 arr[j] 를 찾아내고 이것이 i 보다 큰 경우에만 count 를 증가시킨다. i보다 작은값도 포함시키면 중복처리 될 수 있으므로..
만약 searchIndex 가 i 이하이고 0 이상이면 조기 종료시킨다.

정렬 = O(n log n)
탐색 = O(n / 2)
총 = O(n log n)

풀이 2. 투 포인터

fun `3273 - 두 수의 합`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val token = java.util.StringTokenizer(br.readLine())
    val arr = IntArray(n){ token.nextToken().toInt() }
    val x = br.readLine().toInt()
    var count = 0

    arr.sort()

    var left = 0
    var right = n - 1

    while(left < right){
        val sum = arr[left] + arr[right]

        when {
            sum == x -> {
                left++
                count++
            }
            sum > x -> right--
            else -> left++
        }
    }

    bw.write(count.toString())
    bw.flush()
    bw.close()
    br.close()
}

정렬 = O(n log n)
탐색 = O(n)
총 = O(n log n)

두 개의 차이는 미미하지만 n 이 엄청나게 커진다면 효과적인 효율을 얻어낼 수 있을 것이다.