16934번: 게임 닉네임

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

 

언어 : Kotlin

 

문제 설명 :

스타트링크에서 매우 재미있는 게임을 만들었다. 이 게임은 정말 재미있다.

게임에는 유저가 접속하는 기능이 있고, 각 유저는 가입할 때, 자신의 닉네임을 정해야 한다. 닉네임은 알파벳 소문자로만 이루어져 있고, 두 유저가 같은 닉네임을 정하는 것도 가능하다.

이 게임은 유저의 닉네임을 이용해서 내부에 저장할 별칭을 만든다. 별칭은 유저에게 보여지지는 않고, 내부에서만 사용된다. 저장 공간을 최소로 하기 위해서 별칭의 길이를 최소로 하려고 한다.

별칭은 유저 닉네임의 접두사(Prefix) 중에서 가장 길이가 짧은 것을 사용한다. 이때, 접두사가 이전에 가입한 닉네임의 접두사가 아니어야 한다. 가능한 별칭이 없는 경우에는 유저가 가입한 시점까지 같은 닉네임으로 가입한 사람의 수 x를 계산해야 한다. x가 1인 경우에는 닉네임을 별칭으로 사용하고, x가 2 이상인 경우에는 닉네임의 뒤에 x를 붙여서 별칭으로 사용한다.

예를 들어, 닉네임을 "baekjoon"으로 정한 유저가 가입하면, 이 유저의 별칭은 "b"가 된다. 

그 다음, 닉네임이 "startlink"로 정한 유저가 가입하면, 이 유저의 별칭은 "s"이다. "bakejoon"이 닉네임인 유저가 가입하면, 별칭은 "bak"가 되고, "beakjoon"인 유저가 가입하면, 별칭은 "be"가 된다. 마지막으로 "baekjoon"으로 유저가 가입하면 별칭은 "baekjoon2"가 된다.

유저가 가입한 순서대로 닉네임이 주어졌을 때, 각 유저의 별칭을 구해보자. 위의 규칙을 이용해 별칭을 정하면 두 유저가 같은 별칭을 갖는 것도 가능하다.

 

입력 :

첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다.

 

출력 :

유저가 가입한 순서대로 별칭을 한 줄에 하나씩 출력한다.

 

제한 사항 :

• 시간 제한 : 1초
• 메모리 제한 : 512MB

 

입출력 예 :

입력	출력
5 baekjoon startlink bakejoon beakjoon baekjoon	b s bak be baekjoon2
7 codeplus startlink beakjoon baek baekjoon baek codingwiki	c s b ba baekj baek2 codi
6 abcd ab ab a a ab	a ab ab2 a a2 ab3

 

풀이 : 

트라이 자료구조를 사용해 구현한다.

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

val map: MutableMap<String, Int> = mutableMapOf()

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

    val n = readLine().toInt()
    val trie = Trie()
    for (i in 0 until n) {
        val nickname = readLine()
        bw.appendLine(trie.insert(nickname))
    }

    bw.flush()
    bw.close()
}

class Trie(private val root: TrieNode = TrieNode()) {
    fun insert(key: String): String {
        var cur = root
        var k = key.length
        var flag = false

        for (i in key.indices) {
            val c = key[i]

            if (!cur.children.containsKey(c)) {
                cur.children[c] = TrieNode()

                if (!flag) {
                    k = i + 1
                    flag = true
                    cur.count++
                }
            }

            cur = cur.children[c]!!
        }

        if (!map.containsKey(key)) {
            map[key] = 1
            return key.substring(0, k)
        } else {
            map[key] = map[key]!! + 1
            return key.substring(0, k) + map[key]
        }
    }
}

class TrieNode {
    val children = HashMap<Char, TrieNode>()
    var count = 0
}