[BOJ 16934, Java] Game Nickname

Problem Link

BOJ 16934

Categories

Data Structures, Sets and Maps Using Hashes, Strings, Trees, Tries

Description

Personally, I feel I’m not very good at string problems and think I need to study a bit harder, but this problem could be solved using the trie algorithm.

There were plenty of test cases, so checking for counterexamples wasn’t difficult, but if the examples hadn’t been so clean, this problem would have been a real headache...

Since I hadn’t implemented tree-based structures in Java before, it took me a bit of time, but let’s take pride in the fact that I implemented it without any outside help!

Solution Code

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();

    }

}