[Programmers] 전화번호 목록 (Java)

전화 번호 목록

programmers.co.kr/learn/courses/30/lessons/42577

HashMap 으로 풀이

모든 전화번호를 HashMap 에 넣고 2중으로 다시 순회해서 확인하는 식으로 했다. 조건에 phone_book의 길이는 1 이상 1,000,000 이하입니다. 라고 적혀 있어서 효율성 테스트에서 실패할 줄 알았는데, 생각보다 최대 사이즈가 크지 않은 모양이었다. (그래도 혹시 몰라서 주어진 phone_book 을 정렬했다.)

 

자기 자신 (같은 인덱스 참고) 을 보고 잘못 판단할 수 있기 때문에 HashSet 이 아닌 HashMap 으로 value 값엔 인덱스를 넣어 구현하였다.

import java.util.*; 

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        HashMap<String, Integer> map = new HashMap<>();
        for (int i = 0; i < phone_book.length; i++) {
            if (map.containsKey(phone_book[i])) {
                return false;
            }
            map.put(phone_book[i], i);
        }
        
        for (Map.Entry<String, Integer> e1 : map.entrySet()) {
            for (Map.Entry<String, Integer> e2 : map.entrySet()) {
                if (e1.getValue() == e2.getValue()) {
                    continue;
                }
                if (e1.getKey().startsWith(e2.getKey()) || e2.getKey().startsWith(e1.getKey())) {
                    return false;
                }
            }    
        } 
        return true;
    }
}