백준 5052 - 전화번호 목록
Updated:
Java
5052 번 - 전화번호 목록
문제
접근 방법
입력으로 들어오는 문자열들마다 이전에 다른 문자열이 현재 문자열의 접두어인지 확인해야하는 과정을 거쳐야한다.
길이 순으로 문자열 정렬
먼저, 접두어가 되려면 앞서 나온 문자열들은 현재 문자열의 길이보다 짧거나 같아야 한다.
따라서 Collections.sort()를 해주어, 길이 순으로 정렬한다.
접두어 비교
이제 짧은 문자열 부타 하나씩 이전 문자열 중에 접두어가 있는지 확인한다.
먼저 생각할 수 있는 방법은, 현재 문자열의 길이를 len이라고 하면, 1부터 len까지 String.subString으로 자르면서 이전에 있는 문자열 중 접두어가 될 수 있는 문자열을 찾는다.
하지만 이 방법은 Test Case의 개수 x 총 비교해야할 문자열 개수 : ((1 + n) x (n/2)) / 2 x 전화번호의 최대 길이 10 == 50 x 25002500 x 10으로 시간초과를 유발한다.
따라서 HastSet을 사용하였는데, HashSet의 Contains 시간 복잡 도는 O(1)이다.
현재 문자열 접두어가 이전에 존재한 문자열에 있는지 Set의 Contains로 확인한다.
따라서 50 x 10000 x 10으로 시간 복잡도를 확 줄일 수 있다.
Set 시간 복잡도
| Class Name | Add | Contains | Next |
|---|---|---|---|
| HashSet | O(1) | O(1) | O(h/n) |
| LinkedHashSet | O(1) | O(1) | O(1) |
| EnumSet | O(1) | O(1) | O(1) |
| TreeSet | O(log n) | O(log n) | O(log n) |
코드
import java.util.*;
import java.io.*;
public class Main {
static int tc, result;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
tc = stoi(br.readLine());
boolean isOk = true;
while(tc-- != 0) {
int n = stoi(br.readLine());
List<String> arrS = new ArrayList<>();
for(int i = 0; i < n; i++) {
arrS.add(br.readLine());
}
// 길이 순으로 문자열 정렬
Collections.sort(arrS, (o1, o2)->{
return Integer.compare(o1.length(), o2.length());
});
isOk = true;
Set<String> phone = new HashSet<>();
String str;
for(int idx = 0; idx < n; idx++) {
str = arrS.get(idx);
// 처음 들어온 문자열(제일 짧은)
if(phone.isEmpty()) {
phone.add(str);
continue;
}
for(int i = 1; i <= str.length(); i++) {
// Set에 존재하는 문자열 중에 접두어가 있는지 확인
if(phone.contains(str.substring(0, i))) {
isOk = false;
}
}
phone.add(str);
}
if(isOk)
System.out.println("YES");
else
System.out.println("NO");
}
br.close();
}
static int stoi(String str) {
return Integer.parseInt(str);
}
}
총평
후기
디테일 부족으로 2번 틀린 문제.. 제출하기 전에 조금 더 유심히 봐야할 필요가 있다.
