BOJ_16934_게임 닉네임 (Java)

[Gold III] 게임 닉네임 - 16934

문제 링크

성능 요약

메모리: 85120 KB, 시간: 508 ms

분류

자료 구조, 해시를 사용한 집합과 맵, 문자열, 트리, 트라이

제출 일자

2024년 9월 22일 20:01:14

문제 설명

스타트링크에서 매우 재미있는 게임을 만들었다. 이 게임은 정말 재미있다.

게임에는 유저가 접속하는 기능이 있고, 각 유저는 가입할 때, 자신의 닉네임을 정해야 한다. 닉네임은 알파벳 소문자로만 이루어져 있고, 두 유저가 같은 닉네임을 정하는 것도 가능하다.

이 게임은 유저의 닉네임을 이용해서 내부에 저장할 별칭을 만든다. 별칭은 유저에게 보여지지는 않고, 내부에서만 사용된다. 저장 공간을 최소로 하기 위해서 별칭의 길이를 최소로 하려고 한다.

별칭은 유저 닉네임의 접두사(Prefix) 중에서 가장 길이가 짧은 것을 사용한다. 이때, 접두사가 이전에 가입한 닉네임의 접두사가 아니어야 한다. 가능한 별칭이 없는 경우에는 유저가 가입한 시점까지 같은 닉네임으로 가입한 사람의 수 x를 계산해야 한다. x가 1인 경우에는 닉네임을 별칭으로 사용하고, x가 2 이상인 경우에는 닉네임의 뒤에 x를 붙여서 별칭으로 사용한다.

예를 들어, 닉네임을 "baekjoon"으로 정한 유저가 가입하면, 이 유저의 별칭은 "b"가 된다.

그 다음, 닉네임이 "startlink"로 정한 유저가 가입하면, 이 유저의 별칭은 "s"이다. "bakejoon"이 닉네임인 유저가 가입하면, 별칭은 "bak"가 되고, "beakjoon"인 유저가 가입하면, 별칭은 "be"가 된다. 마지막으로 "baekjoon"으로 유저가 가입하면 별칭은 "baekjoon2"가 된다.

유저가 가입한 순서대로 닉네임이 주어졌을 때, 각 유저의 별칭을 구해보자. 위의 규칙을 이용해 별칭을 정하면 두 유저가 같은 별칭을 갖는 것도 가능하다.

입력

첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다.

출력

유저가 가입한 순서대로 별칭을 한 줄에 하나씩 출력한다.

문제 풀이

기본적인 트라이 사용 문제다. 먼저 트라이라는 구조에 대해 공부 후 적용해보았다. 트리 구조로 일치하는 항목에 접근하여 분기가 생길 때 새로 나누어 데이터를 저장한다. isEnd로 끝인지 판별 가능한 변수도 넣어주었다.(이 문제에선 사실 필요없지만 정석적인 구현 해봄)

나머지는 문제에 맞게 구현해주었다.

최근 입출력 실수 및 선언 위치 실수가 나오는데 주의해야겠다. 급하게 CP식으로 풀지 말고 기본기부터 다시 다져야겠다.

코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	static Trie root;

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		root = new Trie();
		
		for (int i = 0; i < N; i++) {
			String name = br.readLine();
			insertName(name);
		}


		bw.flush();
		bw.close();
		br.close();
	}

	private void insertName(String name) throws IOException {
		Trie trie = root;
		StringBuilder sb = new StringBuilder();
		// 새로운 분기인지 판별 
		boolean flag = false;
		
		for (int i = 0; i < name.length(); i++) {
			int idx = name.charAt(i) - 'a';
			if(!flag) sb.append(name.charAt(i));
			
			// 새로 분기를 만들어야 하면 생성하고 별칭에 추가. 
			if (trie.children[idx] == null) {
				flag = true;
				trie.children[idx] = new Trie();
			}

			trie = trie.children[idx];
		}
		
		trie.isEnd = true;
			if(trie.count == 0)  trie.count++;
			else {
				String x = String.valueOf(++trie.count);
				sb.append(x);
			}
		bw.write(sb.toString() + "\n");
	}

}

class Trie {
	Trie[] children = new Trie[26];
	int count;
	boolean isEnd;

	Trie() {
		this.isEnd = false;
		for (int i = 0; i < 26; i++) {
			children[i] = null;
		}
		this.count = 0;
	}
}