[BOJ - 28353] [백준 - 28353] 고양이 카[Silver - 3] [Solved by Kotlin]

문제 설명

찬우는 친구들과 고양이 카페에 가려 한다.

고양이 카페에는 N마리의 고양이가 있다. i번째 고양이의 무게는 w_i이다. 찬우와 친구들은 모두 고양이를 사랑하기 때문에 무릎 위에 고양이를 정확히 2마리 데리고 있으면 행복해진다. 하지만 허약한 찬우와 친구들은 데리고 있는 두 고양이의 무게의 합이 k를 넘는다면 버티지 못할 것이다.

각 고양이의 무게와 한 명이 버틸 수 있는 최대 무게 k가 주어질 때 최대 몇 명이 행복해질 수 있는지 구해보자.

입출력 예

입력

첫째 줄에 정수 N과 K가 공백으로 구분되어 주어진다. ( 1 <= N <= 5000 1 <= K <= 10^9) 

둘째 줄에는 각 고양이의 무게를 의미하는 N$N$개의 정수 w1,w2,⋯,w_1, w_2, ..., w_N이 공백으로 구분되어 주어진다. (1≤ wi ≤K)

 

출력    

행복해질 수 있는 사람의 수의 최댓값을 출력한다.

 

 

코드

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*

val bw = BufferedWriter(OutputStreamWriter(System.out))
fun closeBW() {
    bw.flush()
    bw.close()
}

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(" ").map { it.toInt() }
    val list = readLine().split(" ").map { it.toInt() }.sorted()

    var res = 0

    var start = 0
    var end = n - 1

    while (start < end) {
        if (list[start] + list[end] <= k) {
            start++
            end--
            res++
        } else {
            end--
        }
    }

    bw.write("$res")

    closeBW()
    close()
}

 

풀이

최대 무게 K를 버틸 수 있는 2개의 값을 찾는 문제이다.

리스트의 크기가 5000로 이중 for문을 사용하게 되면 5000 * 5000 = 25,000,000 회의 연산이 ( O(n^2))필요하므로 투포인터를 사용하여 시간복잡도를 낮춘다. ( O(N) )

 

start와 end를 통해 양 끝에 포인터를 주어 포인터를 좁혀가며 K의 값을 만족하는 값을 찾는다.

찾지 못하면 start와 end가 만날 때까지 값을 줄여가며 값을 찾는다.