전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

 

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
  • 각 전화번호의 길이는 1 이상 20 이하입니다.
  • 같은 전화번호가 중복해서 들어있지 않습니다.

 

입출력 예제

 

phone_book	return
["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

 

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

 

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

 

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

---

푸는 방법 생각

해시 문제로 나와있는데 해시를 이용한 방법이 감이 안잡혀 주어진 배열을 이용해 2중 반복문을 사용해서 풀이했다. 문자열을 비교하기 위해 subString을 생각했지만 접두사를 비교하는 startsWith 함수가 있다는 것을 이번에 알게되서 적용해보았다. 접두사뿐만 아니라 접미사로는 endsWith 함수도 있다.

 

내 코드

class Solution {
    public boolean solution(String[] phone_book) {

        for(int i  = 0; i < phone_book.length - 1; i++){
            for(int j = i + 1; j< phone_book.length;j++){
                if(phone_book[j].startsWith(phone_book[i]))
                    return false;
                if(phone_book[i].startsWith(phone_book[j]))
                    return false;
            }
        }
        return true;
    }
}

 

다른 사람 풀이

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
            HashMap<String, Integer> hashMap = new HashMap<>();

            for (String number : phone_book) hashMap.put(number, 0);
            for (String key : hashMap.keySet())
                for (int j = 1; j <= key.length() - 1; j++)
                    if (hashMap.containsKey(key.substring(0, j))) return false;
            return true;
    }
}

다른 사람 풀이를 통해 해시를 이용한 방법을 알게 되었다. key값으로 hashMap에 전화번호를 넣고 value로는 0을 넣었다. 다음 for문을 이용해 hashMap에 있는 전화번호(key)를 가져와 substring으로 각 key마다 앞에서부터 하나씩 추가하고 containsKey를 이용해 접두사인지 확인했다.

value에 0을 주고 사용하지 않을거면 HashMap이 아닌 HashSet을 이용해도 될 것 같다.