[Programmers] - 전화번호 목록(HashMap, 해쉬, 해시 충돌)

프로그래머스 문제

해쉬를 사용하지 않았을 때

 public boolean solution(String[] phone_book) {
        boolean answer = true;

        Arrays.sort(phone_book, (String s1, String s2) -> s1.length() - s2.length());
        //[12, 88, 123, 567, 1235]

        for (int i = 0; i < phone_book.length; i++) {
            String target = phone_book[i];
            for (int j = i+1; j < phone_book.length; j++) {
                 if(target.length()==phone_book[j].length()){
                    continue;
                }
            
                String substring = phone_book[j].substring(0, target.length());
                if(target.equals(substring)){
                    return false;
                }
            }
        }
        return answer;
    }

배열의 크기순으로 정렬을 하고 대상타겟의 접두사를 subString으로 자른 후 비교,
또한 중복된 숫자는 없기때문에 같은 배열길이는 검사하지 않음. 하지만 시간초과가 발생. 다른 방법을 고려..(

++해쉬맵을 사용하지 않고도 효율성 통과

   public boolean solution2(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book); /// 정렬
        for(int i=0;i<phone_book.length-1;i++){
            if(phone_book[i+1].startsWith(phone_book[i])){
                answer = false;
                break;
            }
        }
        return answer;
    }

정렬방법을 변경하며 하나의 for문으로 실행.

해쉬맵을 사용했을 때

public boolean solution3(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;
    }

맵에서 키나 값이 있는지 확인하는 함수로 containsKey와 containsValue 가 있다. 여기선 key값을 확인.

효율성 통과한 이유는????

HashMap 조회 성능은 ArrayList보다 좋다.

• HashMap
  HashMap은 Bucket이라는 구조를 가지고 키를 찾는다. Bucket에는 key로 생성한 Object와 해쉬코드를 쌍으로 들어있다. 해쉬코드에는 순서가 있고 그 순서를 기반으로 값을 검색하기 때문에 키를 빠르게 찾을 수 있다.

해당 문제를 풀어 보며 해쉬맵 구조를 면밀히 봐야 겠다는 필요성이 느껴진다.
성능비교
왜 HashMap검색속도는 Array보다 빠를까?
해쉬충돌및 전략
해쉬맵구조-네이버D2
해쉬맵구조2