[해시] 전화번호 목록

해시-전화번호 목록

java

1. HashMap

• HashMap과 HashSet은 입력된 값(혹은 key를 기준으로)을 자동 정렬한다.
• 나는 번호 길이도 Set을 만들어서 for문을 돌렸다.
  • 번호의 길이가 다양한 경우엔 사실 필요없을 것 같다. (1부터 최대 번호 길이까지 대부분이 포함될 때? 여튼, 데이터 상태에 따라 많이 다를 것 같다.)
• 정답 페이지를 둘러보다가 HashSet 보다 HashMap이 빠르다는 댓글을 보았다. 왜 그런지 찾아볼 예정.
• 효율성 성능만
  • 테스트 3 〉 통과 (86.31ms, 101MB)
  • 테스트 4 〉 통과 (76.96ms, 97MB)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String, Integer> numMap = new HashMap<>();
        HashSet<Integer> keyLenSet = new HashSet();
        for (String num : phone_book) {
            keyLenSet.add(num.length());
            numMap.put(num, 0);
        }

        for (Integer keyLen : keyLenSet) {
            for (String num : phone_book) {
                if (keyLen < num.length()) {
                    if (numMap.containsKey(num.substring(0, keyLen))) return false;
                }
            }
        }
        return true;
    }
}

• 각 번호 길이 Set 없이도 잘 통과한다. 아래와 같이 각 번호를 크기 1 ~ 번호의 길이 - 1 길이까지 반복해 substring 하며 기존의 중복되는 번호가 존재하는지 확인한다.

  for (String num : phone_book) {
      for (int i = 1; i < num.length(); i++) {
          if (numMap.containsKey(num.substring(0, i))) return false;
      }
  }

2. HashSet

• 효율성 성능만
  • 여기서는 HashMap이랑 비슷한 거 같다.
  • 테스트 3 〉 통과 (85.75ms, 102MB)
  • 테스트 4 〉 통과 (84.43ms, 98.3MB)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        HashSet<String> numSet = new HashSet<>();
        HashSet<Integer> keyLenSet = new HashSet();
        for (String num : phone_book) {
            keyLenSet.add(num.length());
            numSet.add(num);
        }

        for (Integer keyLen : keyLenSet) {
            for (String num : phone_book) {
                if (keyLen < num.length()) {
                    if (numSet.contains(num.substring(0, keyLen))) return false;
                }
            }
        }
        return true;
    }
}

3. 다른 분들이 작성한 코드를 참고한 코드다.
   스트링 정렬(크기가 아닌 사전 순으로 정렬)을 사용해서, 앞 뒤 요소끼리만 비교하면 된다!
   어떻게 이런 생각을 해내는 건지 대단하다.

• 효율성 성능만
  • 테스트 3 〉 통과 (349.62ms, 99MB)
  • 테스트 4 〉 통과 (342.16ms, 97.6MB)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);

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

• 위 코드에서 간단한 조건 분기가 하나 없을 뿐, 거의 같은 코드다.
• 효율성 성능만
  • 테스트 3 〉 통과 (388.04ms, 99.1MB)
  • 테스트 4 〉 통과 (271.49ms, 95.7MB)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);

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