[백준 3273번] [Kotlin] 두 수의 합

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

3273번: 두 수의 합

 

난이도 : 실버 3
태그 : 두 포인터, 정렬

 

 

설명

 

수열이 주어질 때, 두 수의 합이 특정 수와 비슷한 수를 찾는 문제입니다.

해당 문제는 투 포인터(두 포인터)를 사용해 풀 수 있을 것 같네요.

 

투 포인터

 

투 포인터 알고리즘은 두 개의 포인터를 사용해 범위 혹은 두 개의 조합을 찾아나가는 방식입니다.

첫 원소와 마지막 원소를 가르킬 bottom / top (혹은 left / right), 두개의 포인터를 선언합니다.

 

만약, 두 수의 합이 목표 수보다 크다면, top 포인터는 감소,

두 수의 합이 목표 수보다 작다면 bottom 포인터를 증가시키면서 범위망을 좁혀 나가며 찾을 수 있습니다

 

 

소스코드

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())
    val arr = Array(n) { st.nextToken().toInt() }
    val x = readLine().toInt()

    arr.sort()

    var t = n - 1
    var b = 0
    var cnt = 0

    while (b < t) {
        val sum = arr[b] + arr[t]

        if (sum == x) {
            cnt++
            t--
        } else if (sum < x) {
            b++
        } else {
            // sum > x
            t--
        }
    }

    println(cnt)
}

 

 

후기

비슷한 문제로, 백준 1253번 좋다 문제가 있습니다.

https://uknowblog.tistory.com/117

[백준 1253번] [Kotlin] 좋다