[Kotlin] 백준 2467 - 용액

백준 2467(골드5) - 용액

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

2467번: 용액

 

 

알고리즘 분류

• 이분 탐색
• 두 포인터

 

1. 소스코드(시초)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Math.abs
import java.lang.Math.min

fun main(args: Array<String>){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val cnt = br.readLine().toInt()
    val nums = br.readLine().split(" ").map { it.toInt() }

    var num1 = 0
    var num2 = 0
    var answer = 1000000

    for(i in 0 until nums.size - 1){
        for(j in i + 1 until nums.size){
            if(answer > abs(nums[i] + nums[j])){
                num1 = nums[i]
                num2 = nums[j]
                answer = min(answer, abs(nums[i] + nums[j]))
            }
        }
    }

    println("$num1 $num2")
}

 

위의 코드는 단순히 이중 for문은 사용한 코드로써 가장 생각하기 쉬운 방법이지만,, 당연히 시초가 날 것이라고

예상했기때문에 바로 다음 방법을 생각하였다.

 

2. 정답 코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Math.abs

fun main(args: Array<String>){
    val br = BufferedReader(InputStreamReader(System.`in`))
    val cnt = br.readLine().toInt()
    val nums = br.readLine().split(" ").map { it.toInt() }

    var left = 0
    var right = cnt - 1
    var min = Int.MAX_VALUE
    var cLeft = 0
    var cRight = 0

    while(left < right){
        var compare = nums[left] + nums[right]

        if(min > abs(compare)){
            min = abs(compare)
            cLeft = nums[left]
            cRight = nums[right]
        }

        if(compare == 0){
            break
        }

        if(compare < 0) left++ else right--
    }

    println("$cLeft $cRight")
}

 

---

 

3. 해설

 

사용한 알고리즘은 투 포인터 알고리즘이다.

 

var compare = nums[left] + nums[right]

 

왼쪽과 오른쪽을 가리키는 변수를 만들어서 각각의 포인터가 가리키는 부분의 값을 더한 값을 저장하고 있는 compare 변수를 만든다.

 

if(min > abs(compare)){
      min = abs(compare)
      cLeft = nums[left]
      cRight = nums[right]
}

 

위에서 만들었던 compare 변수를 절댓값을 취하고 난 뒤 min 변수와 비교하여 더 작을 경우 변수들의 값을 바꾼다.

 

if(compare < 0) left++ else right--

 

마지막으로 compare의 변수가 0보다 작으면 left++ 를, 0보다 크면 right— 를 한다.