[백준] 1764 (듣보잡)

#1 알고리즘

#1-1 개요

먼저, Input으로부터 '듣지 못한 사람'들을 읽어 들여 명단을 만든다. 그리고 '보지 못한 사람'들을 한 명씩 읽어 들이며, '듣지 못한 사람'의 명단에 존재하는지 확인한다. 존재한다면, 해당 이름을 '듣지도 보지도 못한 사람' 명단에 추가한다. 마지막으로, '듣지도 보지도 못한 사람' 명단을 (사전 순으로) 정렬한다.
 

#1-2 배열 대신 HashSet 사용

Hash table - Wikipedia

'듣지 못한 사람'들을 저장하기 위한 데이터 타입을 HashSet으로 둔다. '보지 못한 사람'과의 교집합을 찾기 위해서는 '듣지 못한 사람' 명단에서 검색을 수행할 필요가 있는데, HashSet의 경우 검색의 시간복잡도가 O(1)이기 때문이다. HashSet은 중복을 허용하지 않지만, 문제의 조건에서 '듣지 못한 사람'들 간 중복은 없다고 했으므로 상관 없다.
 

#1-3 병합 정렬

병합 정렬 (Merge Sort)

병합 정렬을 이용해 '듣지도 보지도 못한 사람' 명단을 정렬했다.
 

#1-4 문자열 간 사전 순서 비교

fun isSecondGreaterThanFirst(s1: String, s2: String): Boolean {
    val shorterLength = if (s1.length < s2.length) {
        s1.length
    } else {
        s2.length
    }

    for (i: Int in 0..<shorterLength) {
        if (s1.codePointAt(i) < s2.codePointAt(i)) {
            return true
            
        } else if (s1.codePointAt(i) > s2.codePointAt(i)) {
            return false
            
        } else {
            continue
        }
    }

    // 여기까지 왔으면, 더 긴 쪽이 사전상 더 뒤쪽이다.
    return s1.length < s2.length
}

#1-3에서 두 원소의 대소 비교는 사전 순서에서의 대소 비교로서 이루어져야 한다. 해당 비교를 위 코드로 구현했다.
 

#2 코드 - 코틀린

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

val br = BufferedReader(InputStreamReader(System.`in`))
val bw = BufferedWriter(OutputStreamWriter(System.out))
val deutdos = HashSet<String>()
val deutodoBodos = ArrayList<String>()

fun main() {
    val countInfo = br.readLine().split(" ")
    val deutdoCount = countInfo[0].toInt()
    val bodoCount = countInfo[1].toInt()

    for (i: Int in 0..<deutdoCount) {
        deutdos.add(br.readLine())
    }

    for (i: Int in 0..<bodoCount) {
        val bodo = br.readLine()

        if (deutdos.contains(bodo)) {
            deutodoBodos.add(bodo)
        }
    }

    br.close()

    mergeSort(deutodoBodos, 0, deutodoBodos.size - 1)

    bw.write("${deutodoBodos.size}\n")
    for (name in deutodoBodos) {
        bw.write("${name}\n")
    }

    bw.flush()
    bw.close()
}

fun mergeSort(array: ArrayList<String>, startIndex: Int, endIndex: Int) {

    // (startIndex < endIndex)의 의미: 배열의 크기가 2이상이다.
    if (startIndex < endIndex) {
        val midIndex = (startIndex + endIndex) / 2
        mergeSort(array, startIndex, midIndex)
        mergeSort(array, (midIndex + 1), endIndex)

        merge(array, startIndex, midIndex, endIndex)
    }
}

fun merge(array: ArrayList<String>, startIndex: Int, midIndex: Int, endIndex: Int) {
    // array에서 나뉜 'f'irst 부분을 순회할 인덱스 f
    var f = startIndex // f의 최댓값은 midIndex

    // array에서 나뉜 's'econd 부분을 순회할 인덱스 s
    var s = midIndex + 1 // s의 최댓값은 endIndex

    // 'T'emporary 배열 그리고 이 배열을 순회할 인덱스 t
    val T: Array<String> = Array(endIndex - startIndex + 1) { "" }
    var t = 0

    while (f <= midIndex && s <= endIndex) {

        if (isSecondGreaterThanFirst(array[f], array[s])) {
            T[t++] = array[f++]

        } else {
            T[t++] = array[s++]
        }
    }

    // f의 영역이 남았다면 비워준다
    while (f <= midIndex) {
        T[t++] = array[f++]
    }

    // s의 영역이 남았다면 비워준다
    while (s <= endIndex) {
        T[t++] = array[s++]
    }

    for (i: Int in 0..(T.size - 1)) {
        array[startIndex + i] = T[i]
    }
}

fun isSecondGreaterThanFirst(s1: String, s2: String): Boolean {
    val shorterLength = if (s1.length < s2.length) {
        s1.length
    } else {
        s2.length
    }

    for (i: Int in 0..<shorterLength) {
        if (s1.codePointAt(i) < s2.codePointAt(i)) {
            return true
            
        } else if (s1.codePointAt(i) > s2.codePointAt(i)) {
            return false
            
        } else {
            continue
        }
    }

    // 여기까지 왔으면, 더 긴 쪽이 사전상 더 뒤쪽이다.
    return s1.length < s2.length
}