11652 카드(Kotlin)

 

 

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

11652번: 카드

입력받는 숫자를 HashMap<Long, Int> 형태로 key에 숫자 value에 나온 횟수를 각각 갱신해 주어서 HashMap의 최대값을 찾아서 출력하기만 하면 되는 간단한 문제였습니다.

 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cards = HashMap<Long,Int>()

    repeat(readLine().toInt()){
        val key = readLine().toLong()
        if(cards[key] == null) cards[key] = 1
        else cards[key] = cards[key]!!+1
    }
    print(cards.filterValues { it == cards.maxOf { it.value }}.keys.minOrNull())
}

최초 답안은 다음과 같이 작성하였습니다. 각각 HashMap에 입력받은 값을 갱신하고 HashMap의 value의 최대값을 가지고 있는 key리스트를 분류하고 그중에서도 가장 작은 값의 key를 출력해주었습니다. 

 

하지만, 다음과 같이 시간초과가 나오게 되었습니다. 입력값의 범위가 -2^62 ~ 2^62 이므로 굉장히 크기때문에 발생하는 문제였습니다. 

 

다음과 같이 코드를 바꾸었습니다. 

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val cards = HashMap<Long,Int>()

    repeat(readLine().toInt()){
        val key = readLine().toLong()
        if(cards[key] == null) cards[key] = 1
        else cards[key] = cards[key]!!+1
    }
    val max = cards.maxOf { it.value }
    val keys = cards.filterValues { it == max }.keys
    print(keys.minOrNull())
}

filterValues 내부에서 계속해서 maxOf()함수를 불러서 O(n)만큼의 동작을 계속 해주었기때문에 그만큼 계속해서 탐색 시간이 길어졌고 이로 인해서 같은 동작이지만, 동작 시간이 굉장히 늘어났던 것입니다. 

 

간단한 코드 수정이지만, 평소에도 쓸데없는 동작을 피하는 코드작성을 하도록 유의해야겠습니다!