[programmers] 해시 - 전화번호 목록

HashSet(혹은 HashMap)을 이용함.

 

set 의 중복 원소를 허용하지 않는다는 특징(map에서도 마찬가지)

+

Hashing(임의의 값을 고정 길이 데이터로 변환)

을 결합한 자료 구조이다.

 

-> 해싱한 결과값(digest) 를 배열의 위치(index)로 활용

 

 

다른 전화번호가 어떤 전화번호의 "접두어" 인 경우를 확인하는 문제이다.

맨 처음에는 패턴 검색을 통한 연산을 생각하였으나, 

 

 

위와 같이 phone_book 배열의 길이는 최대 1,000,000 이지만 각 전화번호의 길이는 최대 20이므로, 

시간복잡도에 대하여 어림잡아 계산해 보았을 때 String 자료형의 substring 메소드를 이용하여도 충분하다는 결론을 얻을 수 있었다.

 

 

따라서 다음과 같이 코드를 작성하였다.

 

import java.util.HashSet;

//hash
public class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer=true;

        //HashSet
        HashSet<String> set = new HashSet<>();
        for (int i = 0; i < phone_book.length; i++) {
            set.add(phone_book[i]);
        }

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

}

 

 

 

 

 

---

HashSet & Hashing 에 대하여

자바 [JAVA] - Hash Set (해시 셋) 구현하기 (tistory.com)

자바 [JAVA] - Hash Set (해시 셋) 구현하기

 

 

HashSet

[JAVA] HashSet이란? & 사용법 정리 (tistory.com)

[JAVA] HashSet이란? & 사용법 정리