[프로그래머스 고득점 Kit] 전화번호 목록 - Hash(해시) - Lv2

⭐️ 코드 (HashSet 이용)

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        HashSet<String> hashSet = new HashSet<>();
        for (int i = 0; i < phone_book.length; i++) {
            hashSet.add(phone_book[i]);
        }
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 0; j < phone_book[i].length(); j++) {
                if (hashSet.contains(phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }
        return answer;
    }
}

---

💊 오답 노트

일단 문제가 해시라서 첫 번째 코드는 아래와 같이 작성해 봤다. 하지만 이렇게 작성하면 해시를 쓰나 마나 똑같기 때문에 시간복잡도와 효율성 부분에서 무조건적으로 오류가 발생했다. 다르게 풀어보자...

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        Arrays.sort(phone_book);
        for (int i = 0; i < phone_book.length; i++) {
            int length = phone_book[i].length();
            HashMap<String, String> hashMap = new HashMap<>();
            for (int j = i + 1; j < phone_book.length; j++) {
                String s = phone_book[j].substring(0, length);
                hashMap.put(s, phone_book[j]);
                if (hashMap.containsKey(phone_book[i])) {
                    return false;
                }
            }
        }
        return answer;
    }
}

두 번째 풀이는 그냥 해시를 빼버렸다. 하지만 당연하게도 조건이 100만 개의 원소를 가지는데 이중포문으로 풀면 1조 번의 연산이기 때문에 오류가 발생하는 게 맞다.. 위 코드랑 별반 다를 게 없다. 그래서 일단 이것도 틀렸다.

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        Arrays.sort(phone_book);

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

HashMap을 이용해서 풀어봤다. 이건 정답이지만 굳이 HashMap을 써야할까? 라는 생각이 들었다. HahsSet만 이용해도 될 것 같아서 아래 하나 더 풀이를 남겨보겠다. 시간과 효율성을 한번 체크해 보도록 하자!

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        HashMap<String, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < phone_book.length; i++) {
            hashMap.put(phone_book[i], 0);
        }
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 0; j < phone_book[i].length(); j++) {
                if (hashMap.containsKey(phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }
        return answer;
    }
}

아래가 HashSet을 이용해서 풀어본 식이다. HashSet이 조금 더 빠르긴하다.

나중에 ContainsKey와 Contains의 속도 차이를 알아보도록 해보자.

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;

        HashSet<String> hashSet = new HashSet<>();
        for (int i = 0; i < phone_book.length; i++) {
            hashSet.add(phone_book[i]);
        }
        for (int i = 0; i < phone_book.length; i++) {
            for (int j = 0; j < phone_book[i].length(); j++) {
                if (hashSet.contains(phone_book[i].substring(0, j))) {
                    return false;
                }
            }
        }
        return answer;
    }
}

---

👀 후기

정말 다양하고 많은 코드들이 있는 것 같다. 어떻게 풀어야 할지 살짝 막막하다 ㅎㅎ..