백준 - 좋다(Kotlin) 다른 사람 답안 참고함.

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.

https://github.com/ROUTINE-STUDY/Algorithm

 

저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문의는 댓글 바람.

 

문제 출처 : https://www.acmicpc.net/problem/1253

 

[문제 설명]

문제 이해에서부터 막힌 문제다.

'N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.'

주어진 수들 중에서 두 개의 수에 합으로 만들 수 있으면 좋은 수라는 의미다.

나는 다른 두 수의 합으로 나타낼 수 있다길래. 3 = 1 + 2, 4 = 1 + 3, 5 = 2 + 3 이런 의미인줄 알았다.

아무튼 문제를 이해하고 나서 투포인터 방식으로 제출했는데 틀렸다.

 

[틀린 코드]

fun isGoodNumber(number: Long, numberIdx: Int, array: LongArray): Boolean {
    var left = 0
    var right = array.size - 1

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

        if (number < sum) {
            right--
        } else if (number > sum) {
            left++
        } else {
            return true
        }
    }

    return false
}

그렇다면 왜 틀렸을까?

처음에는 자료형 때문이라고 생각했다.

그러나, 사실 언뜻 보면 수가 10억이라 오버플로우가 날 것 같지만 결국 두 수의 합이므로 최대값은 20억으로 int 범위를 초과하지 않는다.

 

그리고 문제를 다시 읽어봤다.

'수의 위치가 다르면 값이 같아도 다른 수이다.'

만약, 수의 값이 같더라도 자기 자신을 포인터가 가르킨다면 이 수는 좋은 수가 될 수 없다.

따라서, 다음 단계로 진행해야 한다.

 

[수정해서 통과한 코드]

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val n = br.readLine().toInt()
    var answer = 0
    val array = br.readLine().split(" ").map { it.toInt() }.toIntArray()
    array.sort()

    array.forEachIndexed { index, it ->
        if (isGoodNumber(it, index, array)) {
            answer++
        }
    }

    println(answer)
}

fun isGoodNumber(number: Int, numberIdx: Int, array: IntArray): Boolean {
    var left = 0
    var right = array.size - 1

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

        if (number < sum) {
            right--
        } else if (number > sum) {
            left++
        } else {
            if (left == numberIdx) {
                left++
            } else if (right == numberIdx) {
                right--
            } else {
                return true
            }
        }
    }

    return false
}

굉장히 오랜만에 본 투포인터 문제다. 문제 이해를 못해서 다른 사람 접근법을 대충 훑어보고 풀지 않았다면 풀 수 있었을지 모르겠다.

그래도 구현은 코드를 보지 않고도 혼자 했다는데에 의의를 두자.