[백준 1253번] [Kotlin] 좋다

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

1253번: 좋다

 

난이도 : 골드 4
태그 : 자료구조, 해시를 통한 집합과 맵, 두 포인터, 이분 탐색

 

 

설명

N개의 수 중 어떤 수가 다른 두 수의 합일때, 그 수를 좋다고 합니다.

좋은 수의 개수를 찾는 문제입니다.

 

이 분제는 두 포인터 혹은 이분 탐색으로 풀 수 있을 것 같은데,

저는 두 포인터를 사용해 풀이하도록 하겠습니다.

 

left, right 두 개의 포인터를 선언하고,

left + right의 값이 타 값보다 작으면 left를 +1,

left + right의 값이 타겟 값보다 크면 right를 -1

left + right의 값이 타겟 값과 같으면 결과 cnt를 +1 합니다.

주의하실 점은, 다른 두 수의 합으로 표현이라 했으니, left, right에 타겟값이 포함되어 있으면 안됩니다.

 

 

소스코드

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val st = StringTokenizer(readLine())

    val arr = Array(n) { 0L }
    repeat(n) {
        arr[it] = st.nextToken().toLong()
    }
    arr.sort()

    var cnt = 0

    repeat(n) { ptr ->
        var left = 0
        var right = n - 1

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

            if (sum == arr[ptr]) {
                // 투 포인터가 자기 자신을 포함하면 안됨
                if (left == ptr || right == ptr) {
                    if (left == ptr) left++
                    if (right == ptr) right--
                } else {
                    cnt++
                    break
                }

            } else if (sum < arr[ptr]) {
                left++
            } else {
                right--
            }
        }
    }

    println(cnt)
}

 

 

후기

모닝 커피를 마시면서 하루를 시작하듯이,

모닝 코테로 하루를 시작해보는 건 어떨까요.

해보는 중인데 실력 향상엔 이로우나, 정신 건강엔 해로운 것 같습니다.