백준 16934 게임 닉네임

 

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

16934번: 게임 닉네임

1 . 트라이 

문제에 들어가기 앞서 간단히 트라이에 대해 설명하겠다.

트라이는 문자열 검색에 특화된 트리로 다음과 같은 구조를 가지고 있다.

각 노드마다 Map을 가지고 있고, 문자열을 문자단위로 쪼개고 노드에 저장한다.

문자열를 검색하고 삽입하는데 걸리는시간은 O(NlogN)이다.

 

2. 알고리즘

알고리즘은 다음과 같다.

1. 문자열(word)을 문자로 쪼개고 각 문자를 노드에 삽입을 한다.

2. 이 과정에서 이 노드가 첫 리프 노드라면 그 위치를 기억하자.

3. 해당 노드의 맵에 문자열을 저장하고 포인터를 다음 노드로 옮긴다.

4. 1~3 작업을 문자열의 모든 문자에 대해서 처리한다.

5. 작업이 끝나고 난뒤 cntMap에서 word가 있는지 조회한다. 만약 존재한다면 그전에 그 아이디가 사용되었다는 뜻이므로 cntMap 의 word 의 value를 1만큼 증가시킨다. 만약 존재하지 않는다면 처음 그 아이디가 사용되었다는 뜻이다. 

 

 

3. 예시

 

문제의 3번 예시를 가지고 위 알고리즘을 돌려보겠다.

 

0. 초기에는 trie의 루트 하나만 있는 상태다.

 

 

 

1. baekjoon을 트라이에 삽입한다.

삽입시 b가 첫 리프노드 이므로 b의  위치인 0을 기억한다.

cntMap에서 baekjoon을 조회했지만 없으므로 baekjoon만 cntMap에 삽입한다.

기억한 b의 위치를 이용하여 닉네임 b를 리턴해준다.

 

 

2. startlink 삽입

 

삽입시 s 가 첫번쨰 리프노드이므로 s위치 0를 기억한다.

cntMap에서 startlink를 조회했지만 없으므로 startlink 만 삽입해준다.

기억한 s의 위치를 이용하여 닉네임 s를 리턴한다.

3. bakejoon 삽입

 

삽입시 k 가 첫번쨰 리프노드이므로 k위치 2를 기억한다.

cntMap에서 bakejoon를 조회했지만 없으므로 bakejoon 만 삽입해준다.

기억한 k의 위치를 이용하여 닉네임 bak를 리턴한다.

4. beakjoon 삽입

 

삽입시 e 가 첫번쨰 리프노드이므로 e위치 1를 기억한다.

cntMap에서 beakjoon를 조회했지만 없으므로 beakjoon 만 삽입해준다.

기억한 e의 위치를 이용하여 닉네임 be를 리턴한다.

5. baekjoon 삽입

 

삽입시 마지막 노드인 n이 리프노드이다.

cntMap에서 baekjoon을 조회한 결과 1이다. 즉 이전에 1명의 유저가 이 닉네임을 사용했다는 뜻이다.

cntMap의 값을 2로 업데이트 하고  baekjoon2 라는 닉네임을 리턴한다.

 

 

4. 소스 코드

 

import java.util.*;

import java.io.*;

public class Main {
	static class MyScanner {
		StringTokenizer st;
		BufferedReader bf;

		MyScanner() {
			bf = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}

			return st.nextToken();
		}

		int nextInt() {

			return Integer.parseInt(next());
		}
	}

	static class TrieNode {
		Map<Character, TrieNode> map;

		public TrieNode() {
			map = new HashMap<>();
		}

		private boolean isLast;
		int cnt = 0;

		public Map<Character, TrieNode> getMap() {
			return map;
		}

		public void setMap(Map<Character, TrieNode> map) {
			this.map = map;
		}

		public boolean isLast() {
			return isLast;
		}

		public void setLast(boolean isLast) {
			this.isLast = isLast;
		}
	}

	static class Trie {
		private TrieNode rootNode;

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

		}

		String insert(String word) {
			TrieNode thisNode = rootNode;
			int k = word.length();
			boolean flag = false;
			
			for (int i = 0; i < word.length(); i++) {
				char c = word.charAt(i);

				if (!thisNode.map.containsKey(c)) {
					thisNode.map.put(c, new TrieNode());

					if (!flag) {
						k = i + 1;
						flag = true;
						thisNode.cnt++;
					}

				}

				thisNode = thisNode.map.get(c);

			}

			if (!cntMap.containsKey(word)) {
				cntMap.put(word, 1);
				return word.substring(0, k);
			} else {
				cntMap.put(word, cntMap.get(word) + 1);
				return word.substring(0, k).concat(Integer.toString(cntMap.get(word)));
			}

		}

	}

	static Map<String, Integer> cntMap;

	public static void main(String[] args) {
		
		MyScanner sc = new MyScanner();
		int N = sc.nextInt();
		Trie trie = new Trie();
		cntMap = new HashMap<>();
		
		for (int i = 0; i < N; i++) {
			String word = sc.next();
			System.out.println(trie.insert(word));

		}
	}

}