백준 20366 같이 눈사람 만들래? Kotlin (투 포인터)

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

20366번: 같이 눈사람 만들래?

문제

언니! 똑...똑똑...똑똑! 같이 눈사람 만들래~? ♪

언니 엘자와 동생 안나에게는 N개의 눈덩이가 있다. 각 눈덩이 i (1 ≤ i ≤ N)의 지름은 Hi 이다. 하나의 눈사람은 두 개의 눈덩이로 구성되며, 눈덩이 하나를 아래에 두고 그 눈덩이보다 크지 않은 다른 눈덩이를 쌓아올리는 방식으로 만들 수 있다. 이때, 눈사람의 키는 두 눈덩이 지름의 합과 같다.

엘자와 안나는 눈덩이 N개 중 서로 다른 4개를 골라서 눈사람을 각각 1개씩, 총 2개를 만들려고 한다. 두 자매는 두 눈사람의 키의 차이가 작을수록 두 눈사람의 사이가 좋을 것이라고 믿는다. 우리는 엘자와 안나가 가장 사이좋은 두 눈사람을 만들기 위해서 도와주려고 한다.

주어진 N개의 눈덩이를 이용하여 만들 수 있는 두 눈사람의 키 차이 중 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (4 ≤ N ≤ 600)이 주어진다.

둘째 줄에는 각 눈덩이 i (1 ≤ i ≤ N)의 지름을 의미하는 정수 Hi (1 ≤ Hi ≤ 109)가 공백으로 구분되어 주어진다.

출력

만들 수 있는 두 눈사람의 키 차이 중 최솟값을 나타내는 정수를 출력하라.

알고리즘 분류

• 두 포인터

풀이

투 포인터로 풀 수 있는 문제이다.

처음엔 무지성 4중 포문 돌렸는데 역시나 시간 초과~!

 

우선 엘자든 안나든 눈사람 하나를 먼저 만들고, 나머지의 경우에 대해 생각하는 것을 투 포인터를 사용하면 된다.

주어진 입력을 오름차순으로 정렬하고(O(NlogN)),

눈사람 하나를 먼저 만드는 데에는 2중 포문으로 O(N^2)의 시간 복잡도를 가지고,

i와 j로 눈사람 하나를 만들었다고 하면, 또 하나의 눈사람을 나머지 인덱스들을 투 포인터를 이용해 만드는 데에 O(N)의 시간 복잡도를 가진다.

즉, O(NlogN) + O(N^2 *N)으로 최종적으로 O(N^3)의 시간 복잡도를 가진다.

 

위의 풀이를 좀 자세히 설명하면, i와 j로 눈사람을 하나 만들었다고 하면 i와 j를 제외한 나머지 인덱스로 하나의 눈사람을 더 만들어야 한다. 이때 i와 j로 만든 눈사람을 A, 나머지 인덱스로 만든 눈사람을 B라고 할 때, A-B가 0보다 작다면 B가 더 작아져야 하고, A-B가 0보다 크다면 B가 더 커져야 한다.

예를 들어 주어진 입력을 정렬하고, i와 j가 2,3이라고 하면

2 3 5 5 7 

눈사람 A의 크기는 10이다.

여기서 투 포인터 알고리즘을 적용하면 

start = 0

end = n-1

start와 end 인덱스의 값은 2,7로 B의 크기는 9이다.

A-B는 10-9로 0보다 크기 때문에 A-B의 최솟값을 찾기 위해 B의 크기를 더 키우는 것이다.

여기서 배열은 정렬되어있기 때문에 B의 크기를 키우기 위해선 start를 하나 올리면 된다.

코드

import kotlin.math.*
val INF = Int.MAX_VALUE
val br = System.`in`.bufferedReader()
//4<= n<= 600
fun main() = with(System.out.bufferedWriter()){

    val n = br.readLine().toInt()
    val arr = br.readLine().split(' ').map{it.toInt()}.toIntArray()
    arr.sort()
    var answer=INF
    for(i in 0 until n-1){
        for(j in i+1 until n){
            val sum1 = arr[i]+arr[j]
            var s =0
            var e =n-1
            while(s<e){
                if(s==i || s==j){
                    s++
                    continue
                }
                if(e==i || e ==j){
                    e--
                    continue
                }
                val sum2 = arr[s]+arr[e]
                val result = sum1-sum2
                if(result<0){
                    e--
                }
                else if(result>0){
                    s++
                }
                else{
                    write("0")
                    close()
                    return
                }
                answer = answer.coerceAtMost(abs(result))
            }
        }
    }
    write("$answer")
    close()
}