[백준 2470] [Kotlin] 두 용액

 

 

백준 2470 두 용액

 

난이도 : 골드 5
태그 : 정렬, 이분 탐색, 투 포인터

 

문제 링크 : https://www.acmicpc.net/problem/2470

2470번: 두 용액

 

 

소스코드

import kotlin.math.abs

fun main() {
    val testCase = readLine()!!.toInt()
    val nums = readLine()!!.toString().trim().split(" ").map { i -> i.toInt() }.sorted()

    var min = Int.MAX_VALUE
    var left = 0
    var right = testCase - 1
    var sLeft = 0
    var sRight = testCase - 1

    while (left < right) {
        val v = nums[left] + nums[right]

        if (min > abs(v)) {
            min = abs(v)
            sLeft = left
            sRight = right

            if(v == 0) break
        }

        if (v > 0) right-- else left++
    }
    print("${nums[sLeft]} ${nums[sRight]}")
}

문제 풀이

개요

문제 태그에도 나와있듯이, 정렬과 투 포인터 알고리즘을 사용하여 해결할 수 있다.
투 포인터 알고리즘이란, 양쪽에서 범위 값을 좁혀 목표값을 찾는 알고리즘을 의미한다.


위 코드에서는 nums배열의 탐색 시작과 끝 부분을 left, right로 설정하여 점차 탐색 범위를 좁혀간다.

코드

    val nums = readLine()!!.toString().trim().split(" ").map { i -> i.toInt() }.sorted()

readLine() 을 통해 입력을 받고,
split("") 을 통해 각 입력값을 배열에 넣으려 했지만,
String값을 split("")으로 분배하였더니 배열 양 ["","-2","4","-99",""]와 같이 양끝에 쓰레기 값이 들어갔다.
따라서 split("")을 해주기 전에 trim() 으로 공백을 제거하였다.


배열에 들어갈 값이 String 값이니 int형으로 변환하는 작업이 필요하다.
map(i -> i.toInt()} 를 통해 각 값을 int로 형변환을 시켰고, 마지막으로 sorted() 를 통해 정렬하였다.

이제 두 포인터 (left, right) 를 통해 목표값(0에 가장 가까운 값)을 찾아나가면 된다.

      if (min > abs(v)) {
            min = abs(v)
            sLeft = left
            sRight = right

            if(v == 0) break
        }

두 값의 합(v)가 기존 최소값(min)보다 작다면, min을 새로운 v값으로 대체한다.

 

        if (v > 0) right-- else left++

num[left] + num[right]가 0보다 크면 양 끝값의 합이 더 작아져야 한다. 따라서 right를 줄인다.

num[left] + num[right]가 0보다 작다면, 양 끝값의 합이 더 커져야 하므로 left를 증가시킨다.

양쪽으로 좁혀져 오는 포위망은 목표값을 찾아낼 것이다.