[프로그래머스] 전화번호 목록 in JAVA

개요

프로그래머스 고득점 Kit에서 level 2인 전화번호 목록 문제입니다. 이 문제의 유형은 해시맵으로 key, value로 이루어진 해시맵 자료구조를 활용해야한다는 힌트가 주어집니다.

 

문제의 요구사항은 전화번호가 적힌 문자열 배열에서 어느 한 전화번호가 다른 전화번호의 접두어일 경우를 찾는 것입니다. 중복되는 문자열은 존재하지 않습니다.

 

* 119의 접두어로는 1, 11이 있습니다.

모든 값을 순회하는 해결

public boolean solution2(String[] phone_book) {

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

 

이중 반복문을 사용하여 모든 값을 순회하여 비교하는 단순한 방법입니다. 구현하기에 직관적이지만 시간복잡도가 O(n^2)인 한계가 있습니다. 실제로 이 답안을 제출하면 효율성 테스트에서 실패하는 모습을 볼 수 있습니다.

해시를 활용한 해결

public boolean solution(String[] phone_book) {
    HashSet<String> hashSet = new HashSet<>(Arrays.asList(phone_book));

    for (String str: phone_book) {
      for (int i = 0; i < str.length(); i++) {
        String temp = str.substring(0, i);
        if (hashSet.contains(temp)){
          return false;
        }
      }
    }
    return true;
  }

 

phone_book 문자열 배열을 hashSet에 입력합니다. 이때 HashMap이 아니라 HashSet인 것은 key, value 중 value 값은 사용되지 않기 때문입니다. 

 

주어진 전화번호 목록 phone_book을 순회하면서 전화번호의 0~1번째 글자가 해시셋에 존재하는지 확인, 0~2번째 글자가 해시셋에 존재하는지 확인을 하면서 정답을 찾아가는 방식입니다. 쉽게 말하면 배열과 배열을 비교하는 것은 모든 배열을 순회해야하는 것을 해시셋으로 변경하여 빠르게 찾을 수 있도록 한 것입니다. 이는 hashSet은 검색이 빠르다는 장점을 활용한 것입니다. 

 

배열을 이용한 해결처럼 똑같은 이중 반복문을 사용하기 때문에 효율성에서 큰 차이가 없을 것처럼 보이기도 합니다. 하지만 이중 반복문이긴 하지만 반복하는 전화번호 값은 전화번호 개수와 상관없이 최대 20글자이기 때문에 최악의 경우 O(nm), m은 <= 20으로 보여져 O(n^2)보다는 훨씬 빠릅니다. 또한 hashSet에서 값을 찾아내는 것도 O(1)이기 때문에 이 부분에서도 효율성에 문제가 없습니다. 

 

배운 점

1. 어떠한 값을 빨리 찾아내야할 때(검색) HashMap 자료구조를 사용하면 좋다.

2. HashMap 자료구조를 사용할 때 value가 필요 없을 경우 HashSet을 사용한다.

3. startsWith는 문자열의 접두어인지를 알려주는 메소드이다.