<백준> 비슷한 단어(Gold 4)

[백준]

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

[깃허브]

ForCodeKata/baekjoon 문제집/2179 비슷한 단어 at main · heesoo-park/ForCodeKata

제출 결과

---

문제는 아주 간단했다.

그냥 앞에서부터 체크하면서 가장 길게 알파벳이 동일한 두 단어를 고르면 되는 거였다.

그래서 처음에는 완전탐색을 했다.

물론 그냥 하면 안 될 거 같아서 입력 받을 때 중복을 추가하지 않는 것을 했는데 시간제한을 거의 딱 맞춰서 통과했다.

이 방법은 아닌 것 같아서 다른 사람들의 풀이를 보며 어떤 방법이 있나 확인하는 시간을 가졌다.

 

그랬더니 크게 2가지가 나왔다

하나는 HashMap을 쓰는 것이고 다른 하나는 정렬을 한 후 List나 Set을 사용하는 방식이었다.

 

나는 후자를 선택하여 다시 문제를 풀어갔다.

정렬을 하고나니 따로 반복문을 두번 돌릴 필요없이 한번만 돌리고 바로 옆에 있는 단어들끼리만 체크를 할 수 있었다.

그리고 접두어 길이를 체크하고 저장되어있는 것보다 길다면 MutableSet을 초기화하고 넣어주는 과정을 했다.

이게 왜 필요한지 이해가 되지 않아서 이 부분을 제거하고 그냥 이전에 완전탐색하듯이 무조건 큰 것만 저장했더니 틀렸다고 결과가 나왔다.

아마 정렬된 상태에서 구한 접두어가 가장 긴 것만 가지니까 같은 길이를 가지는 접두어를 체크할 수 없어 기본 상태에서 체크를 할 때 같은 길이이면서 가장 먼저 나오는 케이스에서 넘어가기 때문이지 않나 생각이 들었다.

 

그래서 다시 MutableSet을 초기화하고 넣어주는 과정과 같은 길이일 때는 그냥 넣어주는 과정을 추가해줬다.

그리고 기본 상태의 단어들을 하나씩 접두어 모음을 돌면서 가장 먼저 나오는 것을 저장하여 그걸 출력하도록 했다.

드디어 정답이 되었고 시간의 차이가 2배이상이 났다.

 

다 하고 느끼는 건 입력 받을 때 중복 검사도 안 해도 되지 않을까 싶다는 거다.

왜냐면 같은 접두어 길이를 가지고 있을 때는 그냥 Set에다가 넣기 때문에 어짜피 중복이라 무시되기 때문이다.

중복 검사만 지웠더니 마지막으로 제출한 것보다 3배가 또 줄었다...

 

해당 방법으로 작성한 코드는 다음과 같다.

import java.io.*
import java.util.*

fun main(args: Array<String>) {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val sb = StringBuilder()
    
    val n = br.readLine().toInt()
    val words = mutableListOf<String>()
    
    repeat(n) {
        words.add(br.readLine())
    }
    
    val sortedWords = words.sorted()
    
    var max = 0
    var prefixSet = mutableSetOf<String>()
    for (i in 0 until n - 1) {
        var cnt = 0
        val minLen = minOf(sortedWords[i].length, sortedWords[i + 1].length)
        for (k in 0 until minLen) {
            if (sortedWords[i][k] != sortedWords[i + 1][k]) break
                
            cnt++
        }
            
        if (max == cnt) prefixSet.add(sortedWords[i].substring(0, cnt))
        if (max < cnt) {
            prefixSet = mutableSetOf()
            prefixSet.add(sortedWords[i].substring(0, cnt))
            max = cnt
        }
    }
    
    var prefix = ""
    for (i in words) {
        if (prefix == "") 
        {
            for (j in prefixSet) {
                if (i.length >= j.length && i.substring(0, j.length) == j) {
                    prefix = j
                    sb.append(i + "\n")
                    break
                }
            }
        } else {
            if (i.length >= prefix.length && i.substring(0, prefix.length) == prefix) {
                sb.append(i)
                break
            }
        }
    }
    
    println(sb)
}