[백준] 16934번 게임 닉네임

문제 설명

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

문제 풀이

• trie 자료구조를 이용하여 풀이하였다.
• trie insert 함수를 활용해서 insert시 해당 닉네임 별칭을 리턴하도록 구현하였다.
• Node의 isEnd 변수를 int로 놓고 해당 노드에서 insert가 종료된 갯수를 저장하도록 했다. (동일 문자열의 갯수)
• 자세한 로직은 아래 코드 참조

소스 코드 (JAVA)

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

class Main {
    public static BufferedWriter bw;
    public static BufferedReader br;
    public static int N;

    public static class Node {
        Map<Character, Node> child = new HashMap<>();
        int isEnd = 0;
    }

    public static class Trie {
        Node root = new Node();

        public String insert(String in) {
            Node node = root;
            StringBuilder result = new StringBuilder();
            boolean endFlag = false;
            for (int i = 0; i < in.length(); i++) {
                //해당 자식 노드 존재할때
                if (node.child.get(in.charAt(i)) != null) {
                    node = node.child.get(in.charAt(i));
                    result.append(in.charAt(i));
                }
                //해당 자식 노드 없을때
                else {
                    Node next = new Node();
                    node.child.put(in.charAt(i), next);
                    node = next;
                    if (!endFlag) {
                        result.append(in.charAt(i));
                        endFlag = true;
                    }
                }
            }
            if (node.isEnd == 0) {
                node.isEnd = 1;
                return result.toString();
            }
            else {
                node.isEnd += 1;
                return result.append(node.isEnd).toString();
            }


        }
    }

    public static void main(String[] args) throws IOException {
        bw = new BufferedWriter(new OutputStreamWriter(System.out)) ;
        br = new BufferedReader(new InputStreamReader(System.in));
        Trie trie = new Trie();
        N = Integer.parseInt(br.readLine());
        for (int n = 0; n < N; n++) {
            String res = trie.insert(br.readLine());
            bw.write(res + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}