[전화번호 목록] - 42577

문제 링크입니다.

코딩테스트 연습 - 전화번호 목록 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 전화번호 목록

 

• 어떤 번호가 다른 번호의 접두어이면 false , 아니라면 true를 반환합니다.
• solution 함수는 인자로는 String[] phone_book 을 받고 boolean을 반환합니다.

제한 사항

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

입출력 예제

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

 

문제 접근 방식

phone_book 문자열 배열에서 모든 요소를 돌며 접두어가 phone_book에 있는지를 확인해줍니다.

요지는 접두어 인데, 2번째 예시를 봅시다.

["12","123","1235","567","88"]

 

여기서 "12" 는 "123"의 접두어입니다. 접두어를 어떻게 가려내는 것이 빠를까요?

 

1. "12" 가 phone_book 에 접두어인지 확인

phone_book 의 모든 요소를 돌면서, 앞의 2글자가 "12"와 정확히 일치하는지 확인하면 됩니다. 

이 경우, 확인하려는 접두어의 길이는 모두 다르기 때문에 phone_book의 값들의 앞자리를 전부 다르게 확인해봐야 합니다.

예를 들어 확인하려는 접두어가 "12" 면 phone_book 배열값들의 앞의 2자리를 확인해 일치 여부를 판단,

확인하려는 접두어가 "152266" 이면 앞 6자리를 확인해야 합니다. 

또 phone_book[i] 의 길이가 접두어의 길이보다 작을수도 있으므로 처리도 해주어야 합니다.

 

이처럼 코드를 짜는것이 불가능한것은 아니지만, 복잡한 코드가 나옵니다.

이를 자바의 HashMap을 이용해 간결하게 코드를 작성할 수 있습니다.

 

 

2. HashMap 

해시맵은 key, value값을 가지는 자바 Collection 클래스의 자료구조입니다. 

 

소스코드

public boolean solution(String[] phone_book) {
    Map<String, Integer> map = new HashMap<>();

    for(int i=0;i<phone_book.length;i++)
        map.put(phone_book[i],i);

    for(int i=0;i<phone_book.length;i++){
        for(int j=0;j<phone_book[i].length();j++){
            if(map.containsKey(phone_book[i].substring(0,j))){
                return false;
            }
        }
    }
    return true;
}

phone_book[i].subString(0,j) :

subString()을 이용해 hashMap에 이 부분문자열을 key로 가지는 녀석이 있는지 조사하면 됩니다.

1번에서 접두어를 미리 정해두고 전체를 탐색하는 것과 다릅니다.

이 subString 은 첫번째 인덱스부터 불러오는 것이기 때문에 이 subString을 key값으로 온전히 갖는 요소가 존재한다면, 

그 요소가  subString을 가지는 요소의 접두어가 됩니다.