2179번: 비슷한 단어

문제 출처 : https://www.acmicpc.net/problem/2179

 

언어 : Kotlin

 

문제 설명 :

N개의 영단어들이 주어졌을 때, 가장 비슷한 두 단어를 구해내는 프로그램을 작성하시오.

두 단어의 비슷한 정도는 두 단어의 접두사의 길이로 측정한다. 접두사란 두 단어의 앞부분에서 공통적으로 나타나는 부분문자열을 말한다. 즉, 두 단어의 앞에서부터 M개의 글자들이 같으면서 M이 최대인 경우를 구하는 것이다. "AHEHHEH", "AHAHEH"의 접두사는 "AH"가 되고, "AB", "CD"의 접두사는 ""(길이가 0)이 된다.

접두사의 길이가 최대인 경우가 여러 개일 때에는 입력되는 순서대로 제일 앞쪽에 있는 단어를 답으로 한다. 즉, 답으로 S라는 문자열과 T라는 문자열을 출력한다고 했을 때, 우선 S가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력하고, 그런 경우도 여러 개 있을 때에는 그 중에서 T가 입력되는 순서대로 제일 앞쪽에 있는 단어인 경우를 출력한다.

 

입력 :

첫째 줄에 N(2 ≤ N ≤ 20,000)이 주어진다. 다음 N개의 줄에 알파벳 소문자로만 이루어진 길이 100자 이하의 서로 다른 영단어가 주어진다.

 

출력 :

첫째 줄에 S를, 둘째 줄에 T를 출력한다. 단, 이 두 단어는 서로 달라야 한다. 즉, 가장 비슷한 두 단어를 구할 때 같은 단어는 제외하는 것이다.

 

제한 사항 :

• 시간 제한 : 2초
• 메모리 제한 : 128MB

 

입출력 예 :

입력	출력
9 noon is lunch for most noone waits until two	noon noone
4 abcd abe abc abchldp	abcd abc

 

풀이 : 

단어의 중복은 없으니 distinct()를 통해 중복을 제거한다.

중첩 반복문을 통해 A단어와 B단어를 비교한다.

비교함에 있어서 긴 단어를 기준으로 비교하면 IndexOutOfBound 에러가 발생할 것이므로 짧은 단어 길이를 기준으로 비교한다.

 

비교하며 cnt를 증가시키고, 틀리면 비교 반복문을 빠져나와 max와 비교하여 max보다 크다면 더 많이 유사한 것이므로 값을 변경시켜준다.

String 값을 바꿔나가는 것보다 Int값을 바꿔나가는게 메모리에 더 좋을 것으로 Index 값을 저장하여 결과값을 도출한다.

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

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

    var max = 0
    var save: Pair<Int, Int> = Pair(0, 0)
    val arr = Array(readLine().toInt()) { readLine() }.distinct()
    for (i in 0 until arr.lastIndex) {
        val cur = arr[i]

        for (j in i + 1 until arr.size) {
            val next = arr[j]
            var cnt = 0
            val length = cur.length.coerceAtMost(next.length)

            for (k in 0 until length) {
                if (cur[k] != next[k]) break
                cnt++
            }

            if (max < cnt) {
                max = cnt
                save = Pair(i, j)
            }
        }
    }

    save.apply {
        bw.appendLine(arr[first]).append(arr[second])
    }
    bw.flush()
    bw.close()
}