문자열 해싱

프로그래머스에서 다음과 같은 해쉬 관련 문제를 만났다.

문제 설명

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

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

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

제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.

단순하게 접근해보면 이중 for 문으로 전체 검색을 하면서 비교해보면 간단하게 답이 나올것 같다. 실제로 코드를 통과한 다른 사용자들의 코드를 보면 그렇게 작성된 코드가 많다.

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

정렬을 이용해서 조금더 개선된 코드도 있다.

Arrays.sort(phoneBook);
  boolean result = true;
  for (int i=0; i<phoneBook.length-1; i++) {
    if (phoneBook[i+1].contains(phoneBook[i])) {
      result = false;
      break;
    }
  }
  return result;

전화번호를 먼저 정렬한다음 전화번호와 그다음 전화번호를 비교해서 패턴의 포함여부를 판단하는 알고리즘이다.

위 두 방식으로도 충분히 프로그래머스의 기준을 통과할 수는 있지만, 문제 분류가 해시인데 출제자가 원하는 해법이 아닌것 같다. 그럼 올바른 해법이 무엇일까? 답은 hashCode() 매서드를 사용하는 것이다. 자바 String 클래스의 hashCode는 Object의 hashCode를 오버라이드해서 문자열을 고유의 hash 값으로 변경해주는데, 이 hash 값을 사용해서 문자열을 비교하면 문자열 비교와는 비교할 수 없는 속도로 값 비교를 할 수 있게 된다.

hasCode

Returns a hash code for this string. The hash code for a String object ?>is computed as

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

using int arithmetic, where s[i] is the ith character of the string, n >is the length of the string, and ^ indicates exponentiation. (The hash >value of the empty string is zero.)

Overrides:
hashCode in class Object
Returns:
a hash code value for this object.
See Also:
Object.equals(java.lang.Object), System.identityHashCode(java.lang.>Object)

// hashCode() 를 사용한 코드
  boolean answer = true;

  Loop :
  for(int i = 0; i < phone_book.length; i++){
      for(int j = 0; j< phone_book.length; j++){
          if ( i != j){
              String sourceStr = phone_book[i];
              int sourceStrLength = sourceStr.length();
              int sourceStrHashCode = sourceStr.hashCode();

              String targetStr = phone_book[j];
              if(targetStr.length() >= sourceStrLength){
                  targetStr = targetStr.substring(0, sourceStrLength);
                  int targetStrHashCode = targetStr.hashCode();

                  if(sourceStrHashCode == targetStrHashCode){
                      answer = false;
                      break Loop;
                  }
              }               
          }
      }
  }

  return answer;