[프로그래머스] 전화번호 목록, 알고리즘 문제풀이, Hash, 해시

이전에 파이썬으로 풀었던 방식은,

정렬 후에 두개의 for 문을 사용하되 해당 순서의 길이보다 긴 것들만 찾아보는 식으로 풀었었다.
21년 3월 효율성 테스트케이스 추가되면서 안되는 듯해서 연습하다가 java로 다시 풀었다.

Hash 문제라서 HashSet을 사용했는데,

단어 하나하나에서 각 전체의 substring을 구하는건 비효율적으로 보였으나,

문자열 자체를 비교하는 것 보다는, substring 에서 잘라낸 문자열을 hash 에 있는지 없는지 확인하는 것으로 찾는 것이 더 빨랐다.

package algorithm_sites.programmers;

import java.util.HashSet;

public class hash_02_phone_number_prefix {

    public static void main(String args[]) {

        PhoneNumberPrefix solution = new PhoneNumberPrefix();

//        String[] phone_book = new String[] {"123", "456", "789"};
        String[] phone_book = new String[] {"12","123","1235","567","88"};
        boolean result = solution.solution(phone_book);

        System.out.println(result);
    }

}

// HashSet
class PhoneNumberPrefix {
    public boolean solution(String[] phone_book) {
        HashSet<String> set = new HashSet<>();

        for (int i = 0; i < phone_book.length; ++i) {
            set.add(phone_book[i]);
        }

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

        return true;
    }
}

예로, 아래에 stream 비교하는 횟수는 훨씬 적지만 문자열 비교 자체에서 시간이 많이 걸려서 통과 못하는 케이스가 있는 코드를 추가한다.

// HashMap
class PhoneNumberPrefix {
    public boolean solution(String[] phone_book) {
        HashMap<String, String> map = new HashMap<>();

        for (int i = 0; i < phone_book.length; ++i) {
            map.put(phone_book[i], phone_book[i]);
        }

        for (int i = 0; i < phone_book.length; ++i) {
            final int index = i;
            if (map.values().stream()
                    .filter(s -> phone_book[index].startsWith(s))
                    .count() > 1) {
                return false;
            }
        }

        return true;
    }
}