[백준] 16934번 게임 닉네임 (Java)

오랜만에 알고리즘이다... 알고리즘은 꾸준히 해야 하는데, 이 꾸준히라는 게 너무 어려운 것 같다.

 

코딩 테스트를 몇 번 보면서 느낀점이 있었다. "문자열" 문제 진짜 많이 나오는데, 아슬아슬하게 맨날 못 풀고 있는 것 같았다.

그래서 문자열 유형을 한번 혼내주기로 했다.

 

 

16934번 게임 닉네임

---

1. 문제 분석

---

문자열의 Prefix를 확인해야 하고, 이미 포함되어 있는지에 대한 여부도 확인하면서 문제에 접근해야 했다.

여기서 생각났던 알고리즘은 "트라이" 알고리즘이다. (사실 써보고 싶었습니다.)

 

왜 "트라이"인가? 새롭게 추가되는 문자열을 이미 추가되어 있는 문자열의 prefix에 해당하는지 확인을 해야 한다.

문자열 접두어 확인을 할 때는 "트라이" 알고리즘을 선택하면 빠르게 해결할 수 있다.

 

트라이의 생성 시간 복잡도는 주어지는 닉네임 개수(N, 최대 100,000)와 최대 문자열 길이(L, 10)를 고려해 보면 O(N*L)의 시간복잡도로 트라이를 만들 수 있고, 탐색에서는 O(L)의 시간복잡도로 탐색을 할 수 있어서 빠른 생성과 탐색이 가능한 알고리즘이다. (혁-신)

 

 

 

2. 소스코드

---

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

public class Main {
    private static final String NEW_LINE = "\n";
    private static final String BLANK = "";

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        Trie trie = new Trie();
        NicknameCounts nicknameCounts = new NicknameCounts();
        StringBuilder answer = new StringBuilder();

        int N = Integer.parseInt(reader.readLine());
        for (int i = 0; i < N; i++) {
            String nickname = reader.readLine();
            nicknameCounts.insert(nickname);

            int matchedLastIndex = trie.searchMatchLastIndex(nickname);
            if (matchedLastIndex == nickname.length() - 1) { // nickname 전체가 prefix로 존재
                int x = nicknameCounts.getCount(nickname);
                answer.append(nickname).append(x > 1 ? x : BLANK).append(NEW_LINE);
            } else if (matchedLastIndex > -1) { // trie 안에 겹치는 prefix 존재
                answer.append(nickname, 0, matchedLastIndex + 2).append(NEW_LINE);
            } else if (matchedLastIndex == -1) { // trie 안에 겹치는 prefix 없음
                answer.append(nickname.charAt(0)).append(NEW_LINE);
            }

            trie.insert(nickname);
        }
        System.out.println(answer);
    }
}

class TrieNode {
    Map<Character, TrieNode> childNodes;
    boolean isTerminated;

    public TrieNode() {
        this.childNodes = new HashMap<>();
        this.isTerminated = false;
    }
}

class Trie {
    TrieNode rootNode;

    public Trie() {
        this.rootNode = new TrieNode();
    }

    public void insert(String word) {
        TrieNode node = rootNode;
        for (char ch : word.toCharArray()) {
            node = node.childNodes.computeIfAbsent(ch, key -> new TrieNode());
        }
        node.isTerminated = true;
    }

    public int searchMatchLastIndex(String word) {
        int index = -1;
        TrieNode node = rootNode;
        for (char ch : word.toCharArray()) {
            node = node.childNodes.getOrDefault(ch, null);

            if (node == null) {
                break;
            }
            index++;
        }
        return index;
    }
}

class NicknameCounts {
    private final Map<String, Integer> nicknameCounts;

    public NicknameCounts() {
        this.nicknameCounts = new HashMap<>();
    }

    public void insert(String nickname) {
        if (nicknameCounts.containsKey(nickname)) {
            nicknameCounts.put(nickname, nicknameCounts.get(nickname) + 1);
            return;
        }
        nicknameCounts.put(nickname, 1);
    }

    public int getCount(String nickname) {
        return nicknameCounts.getOrDefault(nickname, 0);
    }
}

 

1. 입력된 nickname 전체가 이전에 등록된 닉네임의 prefix로 존재하는 경우
2. 입력된 nickname 일부가 이전에 등록된 닉네임의 prefix로 존재하는 경우
3. 입력된 nickname이 이전에 등록된 닉네임의 prefix로 존재하지 않는 경우

위와 같이 3개의 경우로 나눠서 코드를 작성해봤습니다.

 

(1) 번의 경우 입력된 nickname 전체가 이미 다른 닉네임의 prefix로 존재하기 때문에 동일한 nickname의 개수가 있는지 확인해 보고, 만약 동일한 nickname의 개수가 1보다 큰 경우 "nickname{개수}"를 붙여서 별칭으로 지정해 줍니다. 만약 1보다 작다면 그냥 본인의 닉네임 자체를 별칭으로 사용합니다.

 

(2) 번의 경우 입력된 nickname의 일부가 이미 다른 닉네임의 prefix로 존재하기 때문에 matchedLastIndex를 사용해서 substring을 통해 가장 짧은 prefix를 만들어냈습니다.

 

예를 들어 "abcd"가 이미지 저장되어 있고, "abdef"가 입력된 닉네임이라면 matchedLastIndex는 1이 될 것입니다. 그럼 여기서 가장 짧은 prefix를 잘라내려면 "abd"가 되어야 하는데, substring(0, 1 + 2)으로 잘라낼 수 있습니다.

 

(3) 번의 경우 nickname이 이전에 등록된 어떤 닉네임의 prefix와도 겹치지 않기 때문에 그냥 자신의 nickname을 그대로 별칭으로 사용하면 됩니다.

 

 

 

 

트라이를 최근에 동아리에서 CS 스터디하면서 알게 되었는데, 그때 검색에서 많이 사용되는 알고리즘이라고 해서 한번 문제에 직접 사용해보고 싶었는데, 마침 문자열 문제에 사용할 수 있게 돼서 재미(?) 있었습니다.

 

다시... 백준 스트릭을 연속으로 채우는 그날까지... 화이팅