[baekjoon] #1253: 좋다

Problem link

Binary Search

• Sort number list in ascending order.
• Iterate [0, n - 1] with index i.
• Iterate [0, n - 1] with index j except (i == j) to avoid duplicate position.
• Find nums[i] - nums[j] using binary search.

lateinit var nums: List<Int>

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    nums = br.readLine().split(" ").map { it.toInt() }.sorted()
    
    var answer = 0
    for (i in 0 until n) {
        val candidate = nums[i]
        for (j in 0 until n) {
            if (i == j) continue
            
            val target = candidate - nums[j]
            val result = binarySearch(target, i, j, 0, n - 1)
            if (result != -1) {
                answer++
                break
            }
        }
    }
    bw.write("$answer")

    br.close()
    bw.close()
}

fun binarySearch(target: Int, i: Int, j: Int, s: Int, e: Int): Int {
    if (s > e) return -1

    val mid = (s + e) / 2
    return if (nums[mid] > target) binarySearch(target, i, j, s, mid - 1)
    else if (nums[mid] == target && mid != i && mid != j) mid
    // The reason why we move the range [mid + 1, e] even when we find target but duplicate index is 
    // the number list is sorted and we iterate 0 to (n - 1).
    else binarySearch(target, i, j, mid + 1, e)
}

시간복잡도

O(N^2 * logN)

Two Pointer

• One pointer (low) points 0.
• The other pointer (high) points (n-1).
• Iterate until low >= high.
• Compare target value and sum of two pointers.
• If the target value is smaller than sum value, high--
• If the target value is bigger than sum value, low++
• If the target value is equal to sum value, answer++

lateinit var nums: List<Int>

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val n = br.readLine().toInt()
    nums = br.readLine().split(" ").map { it.toInt() }.sorted()

    var answer = 0
    for (i in 0 until n) {
        val target = nums[i]
        var low = 0
        var high = n - 1
        while (true) {
            if (low == i) low++
            if (high == i) high--
            if (low >= high) break

            val candidate = nums[low] + nums[high]
            if (target > candidate) low++
            else if (target < candidate) high--
            else {
                answer++
                break
            }
        }
    }
    bw.write("$answer")

    br.close()
    bw.close()
}

시간복잡도

O(N^2)