[codeforces][Kotlin] 1360B - Honest Coach

목차

 

 

문제 정보

https://codeforces.com/problemset/problem/1360/B

Problem - 1360B - Codeforces

난이도 : B

유형 : Greedy, Sort

시간 : O(T *(N + NlogN))

 

---

문제 풀이

 운동선수들을  A, B 집단으로 나눠야하고 나누는 기준은 운동선수들 마다 가지고 있는 힘의 정도이다.

 

"A집단의 운동선수들의 힘 중 가장 큰값 - B집단의 운동선수들의 힘 중 가장 작은 값"을 구해야 한다.

 

정렬 후 양 옆의 힘의 값의 차이가 제일 작은 값이 답이다.

 

이해를 위해 아래 표를 보자.

 

[정렬 전]

2

1

3

2

4

3

[정렬 후]

1

2

2

3

4

4

 

입력값들을 오름차 순으로 정렬하고 왼쪽은 A집단, 오른쪽은 B집단으로 분리할 수 있다.

정렬된 상태에서 분리 했기 때문에 A집단의 가장 오른쪽 값은 그 집단내에서 가장 큰값이고 -> Max_A

자동적으로 B집단의 가장 왼쪽값은 Min_B 값이다.

 

---

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer

fun solution() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var sb = StringBuilder()
    var t = readLine().toInt()
    while (t-- > 0) {
        var n = readLine().toInt()
        var athletes = IntArray(n);

        var st = StringTokenizer(readLine())
        for (i in 0 until n) {
            athletes[i] = st.nextToken().toInt()
        }

        athletes.sort()

        var min = Integer.MAX_VALUE

        for (i in 1 until n) {
            min = min.coerceAtMost(athletes[i] - athletes[i - 1])
        }

        sb.append(min).append('\n')
    }
    print(sb)
}

fun main() {
    solution()
}