백준 14425 문자열 집합 - [알고리즘] [이분탐색] [hashMap][kotlin]

문제 내용

문제 분석

1. String이 N개 주어진다.

2. 추가로 받는 M개의 string중, 기존 N개와 같은 것이 있는지 확인한다.

3. N개의 String에 같은것이 있는 case의 개수를 출력한다.

 

아이디어

1. 매번 문자열끼리 단순 비교한다.

// worstCase에서 10000번을 10000번 비교하면 10^8으로 1초 미만의 시간이 걸리므로 통과 가능하다.

 

> 추가 아이디어

3. 문자열도 정렬이 가능하므로 이분탐색을 사용하면 검사 속도를 올릴 수 있다.

// 이분탐색이란?

 

4. hashMap을 사용하면 값 비교를 O(1)의 시간 복잡도로 할 수 있다.

// 10000개의 String을 hashing할 때 충돌이 얼마나 발생하는지에 따라 시간이 차이날 수 있다.

풀이

fun solve1() { // Brute force - 4860ms
    val br = System.`in`.bufferedReader()

    var n = 0
    var m = 0
    br.readLine().split(' ').let {
        n = it[0].toInt()
        m = it[1].toInt()
    }

    val s = Array<String>(n){ br.readLine() }


    var result = 0
    repeat(m){
        val str = br.readLine()
        for(tmp in s) {
            if(tmp == str) {
                result++
                break
            }
        }
    }

    br.close()
    print(result)
}

fun solve2() { // binary search - 392 ms
    val br = System.`in`.bufferedReader()

    var n = 0
    var m = 0
    br.readLine().split(' ').let {
        n = it[0].toInt()
        m = it[1].toInt()
    }

    val s = Array<String>(n){ br.readLine() }.apply {
        sort()
    }


    var result = 0
    repeat(m){
        val str = br.readLine()
        if(0 <= s.binarySearch(str)) {
            result++
        }
    }

    br.close()
    print(result)
}

fun solve3() { // hashMap - 356ms
    val br = System.`in`.bufferedReader()

    var n = 0
    var m = 0
    br.readLine().split(' ').let {
        n = it[0].toInt()
        m = it[1].toInt()
    }

    val s = HashMap<String, Int>().apply {
        repeat(n) {
            this[br.readLine()] = 1
        }
    }


    var result = 0
    repeat(m){
        val str = br.readLine()
        if(s.containsKey(str)) {
            result++
        }
    }

    br.close()
    print(result)
}