해시, 전화번호 목록
✍ 레벨 2 의 전화번호 목록 문제 / 프로그래머스
전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
- 구조대 : 119
- 박준영 : 97 674 223
- 지영석 : 11 9552 4421
👉 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.
맨 앞 문자열이 다른 번호의 접두어인가? 를 체크하는 문제
public static boolean solution (String[] phone_book) {
boolean flag = true;
Arrays.sort(phone_book);
// 정렬
// System.out.println(Arrays.toString(phone_book));
for (int i = 0 ; i < phone_book.length; i ++ ){
for (int j = i+1; j < phone_book.length; j ++ ){
if (phone_book[j].indexOf(phone_book[i]) > -1) {
System.out.println(phone_book[j]);
System.out.println(phone_book[i]);
return false;
}
}
}
return flag;
}
** 이렇게 풀었더니, 실패했따. 테스트 13, 테스트 14 / 효율성 3, 4
☁ 효율성에서 떨어지는 이유는 Arrays.sort를 사용하는 것 + 이중 포문을 돌고 있는 중에 break를 거는 분기가 하나 더 있어야 한다고 생각한다.
처음에 :
for (int i = 0 ; i < phone_book.length; i ++ ){
for (int j = i+1; j < phone_book.length; j ++ ){
if (phone_book[j].indexOf(phone_book[i]) > -1) {
flag = false;
break;
}
}
}
☁ 이 방식으로 처리하면, 문제는 테스트 케이스에서 Arrays.sort 한것보다 5개는 더틀렸다.
☁ Arrays.sort 는 왜 효율성이 떨어질까? 왜 테스트 케이스를 5개는 더맞을까? 내부에서 이중포문으로 도는 건 다 마찬가지 아닌가?
☁ 정렬도 정렬이지만 중간에 나온 숫자도 다른 번호 ( 앞에서 나왔던? ) 번호의 접두사에 해당하는 경우가 존재해서 이지 않을까 생각했다.
테스트 케이스 13,14 는 제치고 효율성부터 통과하기로 했다.
Arrays.sort 대신에 Collections.sort(Arrays.asList(phone_book)); 를 써봤는데
마찬가지다.
런타임 에러.
맨 뒤에 숫자가 맨 처음 숫자의 접두사로 될 수 있으니까.
맨 처음 숫자는 고정이라는 말이 문제에 없었으니까..
정렬부터
미련하게 아무 생각없이 Integer로 정렬하지 말자 숫자는 0에서부터 시작한다.
✍ 결국 String 으로 정렬해서 비교 하되, 앞뒤 스트링간의 비교를 추가했다.
☁ Arrays.sort 나 Collections.sort 는 속도 차이가 크게 차이가 나는 것 같지는 않다 정말 큰 컬렉션을 돌리는것이 아니라면? 시간은 나중에 비교해보거나 찾아보자.
✍ 반복문을 2번 이상 돌리지 않는 게 키 포인트인 것 같다.
✍ 시간복잡도라는 개념이 왜 중요한지 다시 한 번 생각해보자.
public static boolean solution (String[] phone_book) {
boolean flag = true;
Arrays.sort(phone_book);
for (int k = 1; k < phone_book.length-1 ; k ++ ) {
String mid = phone_book[k];
String bef = phone_book[k-1];
String aft = phone_book[k+1];
// System.out.println(" mid :: "+mid +" / bef :: " + bef) ;
if ( mid.startsWith(bef) || mid.startsWith(aft) || bef.startsWith(mid) || aft.startsWith(mid)) {
return false;
}
}
return flag;
}
✍ 마지막으로, 테스트는 통과했지만 운이 좋아서 통과한 정답 일 수 있다.
