문제 링크
분류
자료 구조(data_structures), 해시를 사용한 집합과 맵(hash_set), 문자열(string), 트리(trees), 트라이(trie)
설명
개인적으로 문자열 문제에 많이 약하다고 생각하고, 조금 더 열심히 공부해야 한다고 생각하는 편인데 이번 문제는 트라이 알고리즘을 사용하여 해결할 수 있는 문제였다.
예제가 많아서 반례 체크는 어렵지 않았는데 이런 문제가 예제까지 깔끔하지 않았다면 더 골치 아파졌을 것 같다...
자바에서 트리형 구조를 구현해보지 못했던 터라 시간을 조금 소모하긴 했지만 따로 도움을 받지 않고 구현했다는 것에 의의를 두자!
풀이 코드
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();
}
}
24시간은 부족한 게 맞다