🏷️ 카테고리
`#트라이` `#정렬` `#문자열` `#트리`
⏳ 시간복잡도
`O(N)` or `O(N log N)`
📒 해설
문제에서 주어진 N이 크지 않아서 그런지, 정렬로도 쉽게 풀리는 문제였습니다. 처음엔 정렬로 풀고 이후에 트라이로 다시 풀어봤는데, 확실히 트라이가 좋은 성능을 보였습니다. 문제의 핵심은 문자들 간의 관계에서 문자 A가 문자 B의 접두사가 되는 관계가 존재하는가? 입니다. 개인적으로는 정렬로 푼다면 골드 4의 난이도를 보이는 문제는 아니었다고 생각이 듭니다. 아래에서 정렬 풀이와 트라이 풀이에 대해서 각각 알아봅시다.
📜 문제 조건
문제의 조건은 다음과 같습니다.
- 테스트케이스 `T (1<= t <= 50)`
- 전화번호의 수 `N (1 <= N <= 10000)`
- 전화번호의 최대 길이 10
📒 정렬 방식의 풀이
🔍 문제 접근
이 문제를 정렬을 이용해서 푼다면 아주 간단하게 풀 수 있습니다. 바로 Java에서의 String은 사전순으로 정렬되기 때문입니다. 정렬을 하게 된다면, 문제에서 주어진 입력을 다음과 같이 볼 수 있습니다.
911
91125426
97625999
이 상황에서 만약 접두사 관계인 두 문자 (A, B)가 있다면, A 바로 뒤에 B가 위치하게 됩니다. (B 외에도 A를 접두사로 가지고 있다면 아닐 수 있습니다)
그러면 주어진 문자들을 배열에 넣고 정렬을 한 후에, 자기 바로 뒤의 인덱스와 접두사인지만 계산해주면 되겠죠?
🔑 문제 풀이
사용 변수
사용한 변수가 배열 하나일 정도로 간단한 풀이입니다.
String[] arr = new String[n];
접두사관계인지 체크
둘의 관계를 체크하기 위해서는 더 짧은 길이만큼 서로 같은지를 체크하면 되겠죠? 아래 첫번째 메서드는 각각 비교하는 방법을 사용했습니다. 조금 더 간단하게 사용하고자 한다면 두 번째 메서드처럼 `startsWith()`을 사용해도 됩니다. 내부 구현을 보니 그렇게 큰 차이가 없기 때문에, `startsWith()` 메서드를 기억해 두셨다가 사용하면 편할 것 같네요.
static boolean dosePhoneNumberIsStartWith(String phone, String start){
int length = start.length();
if(length > phone.length())
return false;
for(int i = 0; i<length; i++){
if(phone.charAt(i) != start.charAt(i))
return false;
}
return true;
}
static boolean dosePhoneNumberIsStartWith(String phone, String start){
return phone.startsWith(start);
}
public boolean startsWith(String prefix, int toffset) {
char ta[] = value;
int to = toffset;
char pa[] = prefix.value;
int po = 0;
int pc = prefix.value.length;
// Note: toffset might be near -1>>>1.
if ((toffset < 0) || (toffset > value.length - pc)) {
return false;
}
while (--pc >= 0) {
if (ta[to++] != pa[po++]) {
return false;
}
}
return true;
}
전체 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws Exception {
// 코드를 작성해주세요
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int t = 0; t<TC; t++){
int n = Integer.parseInt(br.readLine());
String[] arr = new String[n];
for(int i = 0; i<n; i++)
arr[i] = br.readLine();
Arrays.sort(arr);
String answer = "YES";
for(int i = 0; i<n-1; i++){
String start = arr[i];
String phone = arr[i+1];
if(dosePhoneNumberIsStartWith(phone,start)){
answer = "NO";
break;
}
}
sb.append(answer).append("\n");
}
System.out.println(sb);
}
static boolean dosePhoneNumberIsStartWith(String phone, String start){
int length = start.length();
if(length > phone.length())
return false;
for(int i = 0; i<length; i++){
if(phone.charAt(i) != start.charAt(i))
return false;
}
return true;
}
/* OR
static boolean dosePhoneNumberIsStartWith(String phone, String start){
return phone.startsWith(start);
}
*/
}결과
위에가 접두사 체크를 직접 한 경우고, 아래가 `startsWith()`를 사용한 경우입니다. 이 정도면 큰 차이가 없는 것으로 보이네요.
📒 트라이 방식의 풀이
🔍 문제 접근
이름에서 알 수 있겠지만, 트라이라는 자료구조를 활용해서 문제를 해결하려고 합니다. 트라이에 대한 자세한 설명을 할 수는 없지만, 사전 형태의 구조를 가진다고 생각하시면 될 것 같습니다. 주어진 입력을 트라이 구조로 받으면 아래 그림과 같이 형성이 될 것입니다.
위와 같은 형태를 만든 후, 접두사인지 판단을 하기 위해 몇 가지 조건걸어서 판단하려고 합니다.
바로 현재 도달한 지점(위 그림에서의 원)이 다른 글자의 마지막 지점인지와 현재가 나의 마지막인데 이미 이곳을 온 적이 있는 경우입니다. 트라이에 대해서 잘 모르면 이해하기 어려울 수 있지만, 아래 코드와 함께 봐보시죠.
🔑 문제 풀이
사용 변수
변수라고 하기는 그렇지만, 트라이 자료구조를 표현한 클래스가 전부인 문제입니다. 클래스 내부에 또 다른 트라이를 가지고 있는 배열을 만들어줍니다. 이는 위의 그림에서 한 원에서 다른 원으로 나아가는 것을 표현한다고 생각해 주시면 될 것 같습니다.
static class Trie{
Trie[] dictionary = new Trie[10];
boolean isFinal;
public void add(String word){
(...)
}
}
트라이 구성 및 접두사 체크
아래 코드로 트라이를 구성하며 접두사인지를 체크해줍니다. 아래 종료조건과 그 밑에 마지막이라면... 부분을 살펴보시면 됩니다. 글자를 타고 갈수록 `t = trie;`를 통해 깊은 원으로 접근해서 로직을 수행하게 됩니다.
public void add(String word){
int last = word.length();
Trie t = this;
for (int i = 0; i < last; i++) {
int convertIndex = word.charAt(i) - '0'; // '0~9'에 대한 형변환용
Trie trie = t.dictionary[convertIndex];
// 종료조건
// 나 남았는데 지금 위치가 isFinal인 경우. or나 이번에 끝났는데 이미 왔었네?? 하는 경우
if (t.isFinal || (i == last - 1 && trie != null)) {
flag = true;
return;
}
if (trie == null) {
trie = new Trie();
t.dictionary[convertIndex] = trie; // 없다면 추가
}
// 나 마지막이면 표시
if(i == last-1)
trie.isFinal = true;
t = trie;
}
}
전체 코드
import java.util.*;
import java.io.*;
public class Main {
static boolean flag = false;
public static void main(String[] args) throws Exception {
// 코드를 작성해주세요
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int TC = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int t = 0; t<TC; t++){
int n = Integer.parseInt(br.readLine());
flag = false;
Trie trie = new Trie();
String answer = "YES";
int i = 0;
for (; i < n; i++) {
String word = br.readLine();
if(!flag)
trie.add(word);
if(flag){
answer = "NO";
}
}
sb.append(answer).append("\n");
}
System.out.println(sb);
}
static class Trie{
Trie[] dictionary = new Trie[10];
boolean isFinal;
public void add(String word){
int last = word.length();
Trie t = this;
for (int i = 0; i < last; i++) {
int convertIndex = word.charAt(i) - '0';
Trie trie = t.dictionary[convertIndex];
// 종료조건
if (t.isFinal || (i == last - 1 && trie != null)) {
flag = true;
return;
}
if (trie == null) {
trie = new Trie();
t.dictionary[convertIndex] = trie; // 이게 넣은거임
}
// 나 마지막이면
if(i == last-1)
trie.isFinal = true;
t = trie;
}
}
}
}결과
정렬 방법은 400대였던걸 생각하면 아주 빨라진 걸 확인할 수 있습니다. 트라이 자료구조에 익숙해진다면 한번 해보시는 것도 좋겠네요.
