요약

  • 구름톤 코테1주차 과정의 문제들에 대한 이야기

금요일 문제

  • 솔직히 좀 걸렸습니다. 코틀린으로 코테언어 바꾼지 얼마 안됬다고 변명하기엔.. 그냥 코테실력이 부족했습니다.
  • 단순 구현은 좀 빨리 끝났는데, 이게 자꾸 효율성 테스트에서 Fail 이 발생했습니다.
  • 요즘 효율성까지 보는 문제들을 잘 안풀어서 그런지 그냥 포기할까? 생각을 했고 실제로 금요일에는 포기했습니다. 근데 거기서 끝나면 이런 글을 못썼겠죠? 그냥.. 시간을 왕창 갈아넣어서 겨우겨우 풀었습니다
  • 잡설이 길었는데 코드먼저 보시죠

답은 맞는데 효율성을 통과 못하는 코드

fun main(args: Array<String>) {

    val (count, indexOfAnswer) = readLine()!!.split(" ").map { s -> s.toInt() }
    val st = StringTokenizer(BufferedReader(InputStreamReader(System.`in`)).readLine(), " ")
    
    val list: List<Int> = (1..count)
        .asSequence()
        .map { st.nextToken().toInt() }
        .sortedWith(
            compareByDescending<Int> { countOf1AtBinary(it) }
                .thenByDescending { it }
        )
        .toList()
    print(list[indexOfAnswer - 1])
}

fun countOf1AtBinary(decimalNumber: Int): Int {
    return Integer.toBinaryString(decimalNumber)
        .toCharArray()
        .filter { it -> it == '1' }
        .size
}

효율성을 통과하는 코드

fun main(args: Array<String>) {

    val (count, indexOfAnswer) = readLine()!!.split(" ").map { s -> s.toInt() }
    val st = StringTokenizer(BufferedReader(InputStreamReader(System.`in`)).readLine(), " ")
    val list = mutableListOf<Pair<Int, Int>>()
    for (i in 1..count) {
        val num = st.nextToken().toInt()
        list.add(Pair(num, countOf1AtBinary(num)))
    }
    list.sortWith(
        compareByDescending<Pair<Int, Int>> { it.second }
            .thenByDescending { it.first }
    )
    print(list[indexOfAnswer - 1].first)
}

fun countOf1AtBinary(decimalNumber: Int): Int {
    return Integer.toBinaryString(decimalNumber)
        .toCharArray()
        .filter { it -> it == '1' }
        .size
}

효율성에서 실패하는 원인

  • 위 두 코드에서 효율성이 갈리는 부분은
//효율성 통과
val list = mutableListOf<Pair<Int, Int>>()
for (i in 1..count) {
    val num = st.nextToken().toInt()
    list.add(Pair(num, countOf1AtBinary(num)))
}
list.sortWith(
    compareByDescending<Pair<Int, Int>> { it.second }
        .thenByDescending { it.first }
)

//효율성 실패
val list: List<Int> = (1..count)
    .asSequence()
    .map { st.nextToken().toInt() }
    .sortedWith(
        compareByDescending<Int> { countOf1AtBinary(it) }
            .thenByDescending { it }
    )
    .toList()
  • 원인은… 분석중임다..

요구조건

  • 문제의 요구 조건은 아래와 같았습니다
[문제]
- N개의 10진수 정수가 주어진다. 플레이어에게 정수를 그냥 정렬하는 것은 너무 쉽기 때문에, 아래 기준에 따라 정수를
정렬하기로 한다.
- 10진수 정수를 2진수로 나타냈을 때, 2진수에 포함된 1의 개수를 기준으로 내림차순 정렬한다.
- 1의 개수가 같다면, 원래 10진수를 기준으로 내림차순 정렬한다.
플레이어가 정수를 잘 정렬했을 때, 앞에서 번째에 위치한 수는 어떤 수가 될지 구해보자.
[입력]
첫째 줄에 주어지는 정수와 플레이어가 찾으려는 정수의 위치 가 공백을 두고 주어진다

구름톤 컨테이너 주소