전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.
phone_book | return |
---|---|
["119", "97674223", "1195524421"] | false |
["123","456","789"] | true |
["12","123","1235","567","88"] | false |
입출력 예 #1
앞에서 설명한 예와 같습니다.
입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.
입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다
처음에 해시 맵을 어떻게 사용할까 고민하다가 이중 loop를 만들어서 풀었더니 속도가 1.4ms가 나와 효율성 테스트를 통과하지 못했다.
class Solution {
public boolean solution(String[] phoneBook) {
for(int i=0; i<phoneBook.length-1; i++) {
for(int j=i+1; j<phoneBook.length; j++) {
if(phoneBook[i].startsWith(phoneBook[j])) return false;
if(phoneBook[j].startsWith(phoneBook[i])) return false;
}
}
return true;
}
}
해시맵을 사용하니 풀어보니 0.5ms로 여유롭게 통과할 수 있었다.
import java.util.*;
class Solution {
public boolean solution(String[] phone_book) {
boolean answer = true;
HashMap<String,String> map = new HashMap<String, String>();
for(String phone : phone_book) map.put(phone, "prefix");
for(String phone : phone_book){
for(int i=0; i<phone.length(); i++){
if(map.containsKey(phone.substring(0,i))){
return false;
}
}
}
return answer;
}
}
오늘 중으로 hashmap을 다시 정리해야 겠다.