[백준] 3273번: 두 수의 합 - Kotlin[코틀린]

문제

 

3273번: 두 수의 합

 

---

풀이

 

 입력받은 수열을 오름차순으로 정렬한 후, 두 포인터를 사용하여 원하는 합을 만드는 투 포인터 문제이다. 앞과 뒤에서 시작하는 두 개의 포인터를 조작하여 합을 조절하며 원하는 값에 도달하는데, 합이 목표값보다 크면 뒤의 포인터를 앞으로, 작으면 앞의 포인터를 뒤로 움직입니다. 두 포인터가 만날 때 반복문을 종료해준다.

 

 투 포인터 알고리즘은 한 번의 루프마다 두 포인터 중 하나만 1씩 증가하며, 각 포인터의 합이 목표값이 되면 알고리즘이 종료된다. 따라서 시간복잡도는 $O(N)$이다.

 

---

코드

 

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

    val num = br.readLine().toInt()
    val arr = br.readLine().split(' ').map { it.toInt() }.toIntArray()
    arr.sort()

    val sum = br.readLine().toInt()
    var cnt = 0
    var start = 0
    var end = num - 1

    while (start < end) {
        val tmp = arr[start] + arr[end]
        if (tmp == sum) {
            cnt++
        }
        if (tmp <= sum) {
            start++
        } else {
            end--
        }
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}