풀이 과정
전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질때 어떤 번호가 다른 번호의 접두어인 경우가 있는지 확인을 잘하는게 포인트이다.
phone_book 에 전화번호가 저장이 되어있고 중복된 전화번호는 없다. 그렇다면 어떻게 하면 좋을까?
문제 코드
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
Map<Integer, String> h = new HashMap<>();
for(int i=0; i<phone_book.length; i++){
h.put(i, phone_book[i]); // HashMap에 배열에 있는 값 넣어주기
}
for(int i=0; i<phone_book.length; i++){
for(int j=0; j<phone_book.length; j++){
if(i == j) continue; // 같은 값 비교 방지
if(h.get(i).startsWith(phone_book[j])){
answer = false;
break;
}
}
}
return answer;
}
}
첫 번째 for 문에서 각 전화번호를 HashMap 에 저장하고 키는 인덱스이고 값은 전화번호문자열로 지정했다.
for(int i=0; i<phone_book.length; i++){
h.put(i, phone_book[i]); // HashMap에 배열에 있는 값 넣어주기
}
두번째 for문에서 루프는 각 전화번호에 대해 다른 모든 전화번호의 접두사인지 검사 한다. 이때 if( i == j) countinue 를 이용하여 같은 전화번호끼리 비교하지 않도록 한다.
여기서 중요한건 if(h.get(i).startsWith(phone_book[j])) 는 현재 전화번호가 다른 전화번호의 접두어인 경우 answer를 false로 설정하고 루프를 더 이상 안돌게 해야한다.
for(int i=0; i<phone_book.length; i++){
for(int j=0; j<phone_book.length; j++){
if(i == j) continue; // 같은 값 비교 방지
if(h.get(i).startsWith(phone_book[j])){
answer = false;
break;
}
}
}
이렇게 했을때 문제점이 있다. 각 전화번호를 다른 모든 전화번와 비교하기 때문에 효율이 안나와 테스트에 실패하게 된다. 가장 좋은 방법은 Arrays.sort를 이용하여 전화번호를 정렬 하고 돌리는것이 가장 좋다.
다른 사람 코드
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
// 전화번호를 정렬
Arrays.sort(phone_book);
// 인접한 번호들만 비교
for (int i = 0; i < phone_book.length - 1; i++) {
// 현재 번호가 다음 번호의 접두사인지 검사
if (phone_book[i + 1].startsWith(phone_book[i])) {
return false;
}
}
return true;
}
}
해당 코드 처럼 정렬을 하고 하면 좋지만 이 문제는 해시에 대한 문제이기 때문에 hash에 대한 코드를 가져오면
Hash 이용한 코드 분석
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
Set<String> set = new HashSet<>(Arrays.asList(phone_book));
for (String phone : phone_book) {
for (int i = 1; i < phone.length(); i++) {
if (set.contains(phone.substring(0, i))) {
return false;
}
}
}
return true;
}
}
set<Strin> set = new HashSet<>(Arras.asList(phone_book)); 를 이용하여 전화번호 목록을 HashSet에 추가하여 중복 되지 않게 저장을 해준다. 그 이후 for을 이용하여 각 전화번에 대해 반복하고 if(set.contaions(phone.substring(0,i))) 생성된 접두사가 HashSet 에 있는지 확인하여 존재 한다면 false로 반환하고 발결되지 않으면 true로 반환 해준다. 이렇게 하면
검색은 평균적으로 0(1) 이므로, 전체 시간 복잡도는 0(n * m)이다.
정리
문제를 보고 서로 같은 값이 있는지 없느지 체크해주는 문제라고 생각하고 문제를 풀었다. 하지만 이 문제에는 시간복잡도까지 생각을 해야하고 어떻게 하면 더 효율이 좋을지 생각을 했어야 하는 문제이다. 간단하게 정렬을 한번 해주고 문제를 풀었으면 좋았는데 정렬를 생각안하고 어떻게 하면 이중 for문을 안쓸까? 라는 생각만 하고 있었다. 문제를 좀만 집중해서 보았으면 금방 끝날수 있던 문제인데 너무 어렵게 생각을 했다. 이번에 나의 문제점을 발견 하게 되었다.
1. 시간 복잡도 생각 안했다.
2. 효율 좋은 코드를 생각을 안했다.
3. 문제에 대한 이해도가 부족했다.
앞으로는 문제를 제대로 읽어보고 이 문제가 무엇을 말하는지 파악을 한뒤에 어떻게 하면 효율 좋은 코드를 작성할수 있을지 생각을 하면서 문제를 풀도록 하겠다.