[BOJ 16934, Java] 游戏昵称

题目链接

BOJ 16934

分类

数据结构(data_structures)、基于哈希的集合与映射(hash_set)、字符串(string)、树(trees)、Trie(trie)

说明

我个人觉得自己在字符串题上比较薄弱，觉得应该再加把劲学习一下，而这道题正好是可以用Trie算法解决的。

因为示例很多，反例检查并不难，但如果这种题连示例都不够清晰的话，恐怕会让人头疼得多……

由于之前从未在Java中实现过树型结构，虽然花了一些时间，但能不借助外力独立实现，这一点还是值得肯定的！

解题代码

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

public class Main {

    public static class Node {

        char nowChar;
        String value;
        int count = 0;
        boolean isUnique = true;
        HashSet<Node> childSet;

        // 헤드에 사용하기 위한 정의 방식
        Node() {

            this.childSet = new HashSet<>();
            this.value = "";
            this.isUnique = false;

        }

        // 일반적인 서브노드들을 위한 정의 방식
        Node(char target) {

            this.nowChar = target;
            this.childSet = new HashSet<>();
            this.value = "";

        }

    }

    public static class Trie {

        // 헤드 노드 1개를 보유하고 시작
        Node head = new Node();

        /**
         * 문자열 1개를 트라이 클래스에 추가하는 메서드
         */
        public void addString(String target) {

            Node nowNode = this.head;
            int targetLength = target.length();

            for (int i = 0; i <= targetLength; i++) {

                if (i == targetLength) {

                    nowNode.count += 1;
                    nowNode.value = target;

                } else {

                    boolean hasChild = false;

                    for (Node subNode : nowNode.childSet) {

                        if (subNode.nowChar == target.charAt(i)) {

                            nowNode = subNode;
                            hasChild = true;
                            break;

                        }

                    }

                    if (!hasChild) {

                        Node madeNode = new Node(target.charAt(i));
                        nowNode.childSet.add(madeNode);
                        nowNode = madeNode;

                    }

                }

            }

        }

        /**
         * 문자열의 고유 별칭을 찾아내는 메서드
         */
        public String findUnique(String target) {

            Node nowNode = this.head;
            int targetLength = target.length();
            boolean isFirstTime = true;
            int result = -1;
            int resultCount = -1;

            for (int i = 0; i < targetLength + 1; i++) {

                // 첫 번째로 만나는 고유값이 해당 문자열의 별칭
                if (nowNode.isUnique && isFirstTime) {

                    nowNode.isUnique = false;
                    isFirstTime = false;
                    result = i;
                    resultCount = nowNode.count;

                    // 이후로도 만나는 고유값은 고유값이 아니도록 처리
                } else {

                    if (nowNode.isUnique) {
                        nowNode.isUnique = false;
                    }

                }

                // 마지막 문자까지 확인
                if (i == targetLength) {

                    // 마지막 문자까지 고유값을 체크하지 못한 경우
                    if (result == -1) {
                        result = targetLength;
                        resultCount = nowNode.count;
                    }

                    // 카운팅 갯수에 따른 값을 반환
                    if (nowNode.count == 1) {
                        return target.substring(0, result);

                    } else {
                        return target + resultCount;
                    }

                    // 마지막 문자 이전까지는 트라이 내 탐색 방식으로 진행
                } else {

                    for (Node subNode : nowNode.childSet) {

                        if (subNode.nowChar == target.charAt(i)) {
                            nowNode = subNode;
                            break;

                        }

                    }

                }

            }

            return "ERROR!";

        }

    }

    public static void main(String[] args) throws IOException {

        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));

        // Trie Algorithm

        // 트라이 인스턴스 선언
        Trie nickNameTrie = new Trie();

        // 유저 수 입력
        int userNumber = Integer.parseInt(input.readLine());

        // 모든 유저에 대해 진행
        for (int i = 0; i < userNumber; i++) {

            // 닉네임 입력 및 트라이에 추가
            String nickName = input.readLine();
            nickNameTrie.addString(nickName);

            // 함수를 호출하여 해당 닉네임에 대한 별칭 출력
            if (i == userNumber - 1) {
                output.write(nickNameTrie.findUnique(nickName));

            } else {
                output.write(nickNameTrie.findUnique(nickName) + "\n");
            }

        }

        output.flush();
        output.close();

    }

}