[백준/1764/Kotlin] 듣보잡

문제

문제를 풀 때 시간 복잡도를 생각하고 풀자는 의미에서 이번 포스팅을 하게 되었다. 

이 문제는 "듣도 못한 사람"의 리스트와 "보도 못한 사람"의 리스트 중 중복되는 데이터를 사전 순으로 출력하는 문제이다.

 

트러블 슈팅

1) 시간 초과

처음에 코드를 작성했을 때 출력은 제대로 되었는데 막상 백준에서 돌려보니 시간 초과 문제가 발생하였다.

내가 작성한 코드의 흐름은 아래와 같다.

val neverHeard : MutableSet<String> = mutableSetOf()
val result : MutableSet<String> = mutableSetOf()

repeat(n) {
    neverHeard.add(bufferedReader.readLine())
}

repeat(m) {
    val neverSeen : String = bufferedReader.readLine()
    for (name in neverHeard) {
        if(neverSeen == name) {
            result.add(name)
        }
    }
}

 

"보도 못한 사람"의 이름을 입력할 때마다 이미 입력했던 "듣도 못한 사람"의 이름을 하나하나 확인하였다.

• repeat(m) 바깥 루프 → m번
• 안쪽 for (name in notHearSet) → n번

➡️ 총 O(n * m) 시간이 걸렸다.

그래서 시간 초과가 발생할 수 밖에 없었던 것 같다.

 

2) 탐색 시간 줄이기

val neverHeard : MutableSet<String> = mutableSetOf()
val result : MutableList<String> = mutableListOf()

repeat(n) {
    neverHeard.add(bufferedReader.readLine())
}

repeat(m) {
    val neverSeenName : String = bufferedReader.readLine()
    if (neverHeard.contains(neverSeenName)) {
        result.add(neverSeenName)
    }
}

 

이제 시간을 줄여보자. contains를 활용해서 탐색시간을 O(1)로 줄였다.

 

➡️ 총 O(m) 시간이 걸렸다.

시간이 훨씬 줄어든 것을 확인할 수 있다.

 

3) 코드 예쁘게 쓰기

이번에는 성능 상에는 크게 문제가 없지만 코드를 예쁘게 쓰고 싶어서 기록해본다.

val inputList : List<Int> =  bufferedReader.readLine().split(" ").map { it.toInt() }

val n : Int =  inputList[0]
val m : Int = inputList[1]

 

입력값인 n과 m을 띄어쓰기로 받기 위해 아래처럼 리스트로 만들고 하나하나 변수에 넣어주었다.

 

val (n, m) =  bufferedReader.readLine().split(" ").map { it.toInt() }

그러나 이렇게 구조 분해 선언을 활용해서 한 줄로 나타낼 수가 있다!

 

전체 코드

fun main() {
    val bufferedReader = BufferedReader(InputStreamReader(System.`in`))
    val bufferedWriter = BufferedWriter(OutputStreamWriter(System.out))

    val (n, m) =  bufferedReader.readLine().split(" ").map { it.toInt() }

    val neverHeard : MutableSet<String> = mutableSetOf()
    val result : MutableList<String> = mutableListOf()

    repeat(n) {
        neverHeard.add(bufferedReader.readLine())
    }

    repeat(m) {
        val neverSeenName : String = bufferedReader.readLine()

        if (neverHeard.contains(neverSeenName)) {
            result.add(neverSeenName)
        }
    }

   val sortedList = result.sorted()

    bufferedWriter.write("${sortedList.size}\n")
    sortedList.forEach { name ->
        bufferedWriter.write("$name\n")
    }

    bufferedWriter.flush()

    bufferedReader.close()
    bufferedWriter.close()
}