[백준] 두 용액 - 골드 5 (Kotlin)

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다. 산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다.

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

풀이

처음엔 시작 점과 끝 점을 양쪽 끝에서 부터 좁혀오는 방식을 몰랐다.
그래서 두 점을 첫 번째 인덱스에 두고 시작하려니 결국은 시작 점은 0 ~ N 범위로 반복문을 돌고, 끝 점은 1 ~ N 의 범위로 반복문을 도는 방법밖에 생각이 나지 않아서 이게 왜 투포인터 문제일까 고민하다가 도통 떠오르지 않아 풀이를 검색해보았다.
일단 풀이 방식 자체가 시작 점과 끝 점을 양 끝 인덱스에 놓고 좁혀오는 방식을 써야했고, 그 점은 이해하기에 어려운 부분이 없었다.
하지만 이 문제에서 생각을 좀 해보아야 할 부분은 주어진 배열을 정렬해야 한다는 점이었다.
용액의 값이 양수 혹은 음수이기 때문에 배열을 정렬하게 되면

• [-2, 4, -99, -1, 98]
• [-99, -2, -1, 4, 98]
• [left, -, -, -, right]
  로 정렬이 되고, 시작 점과 끝 점이 가리키는 값들은 각 각 양수와 음수에서 절댓값이 가장 큰 값이 된다.
  이 상태에서 두 값을 더하면 -1 이 나오고, -1 은 음수이기 때문에 두 값 중에서 음수의 값이 더 크다는 뜻이된다.
  따라서, 음수를 가리키는 left 값을 우측으로 한 칸 옮겨주면 정렬된 배열이기 때문에 결과 값이 -1 보다 커질 수 밖에 없다. 또한, 점점 더 작은 값을 더하기 때문에 결과 값의 범위가 줄어든다. (절댓값이 0 에 가까워 진다는 뜻)
  반대로 더한 결과가 양수가 나온다면 양수의 값이 (right 값) 더 크다는 뜻이므로 right 값을 왼쪽으로 한 칸 옮겨주면 결과가 더 작아질 것이다. (마찬가지로 0 에 가까워 진다는 뜻)
  이 부분을 해설을 보지 않고 생각하기가 어려웠다.
  결과적으로, 정렬을 하는 이유가 이해되었다면 코드를 짜는 것은 어렵지 않다.

소스 코드

import kotlin.math.abs

fun main(args: Array<String>) {
    /*
5
-2 4 -99 -1 98
     */
    val n = readLine()!!.toInt()
    val data = readLine()!!.split(' ').map { it.toInt() }.sorted()
    val result = IntArray(2) {0}

    var left = 0
    var right = n-1
    var min = Int.MAX_VALUE

    while (left != right) {
        val sub = data[left] + data[right]
        if (abs(sub) < min) {
            min = abs(sub)
            result[0] = data[left]
            result[1] = data[right]
        }
        if (sub > 0) right--
        else left++
    }

    print("${result[0]} ${result[1]}")
}