[프로그래머스] 전화번호 목록 📖

✍ 첫번째 풀이

💻 코드

class Solution{
    public boolean solution(String[] phone_book) {
        for(int i=0;i<phone_book.length-1;i++){
            for(int j=i+1;j<phone_book.length;j++){
                if(phone_book[i].startsWith(phone_book[j]))
                    return false;
                else if(phone_book[j].startsWith(phone_book[i]))
                    return false;
            }
        }
        return true;
    } // 효율성 테스트 3, 4 -> 시간 초과
}

이 문제는 Hash 문제이지만 처음 봤을 때 Hash로 어떻게 풀어야 할 지 생각이 안나서 다음과 같은 코드로 문제를 풀어보았다.

🖨 채점 결과

📑 풀이 설명

매개변수로 받은 phone_book을 이중 for문을 통해 첫번째 for문의 로컬 변수인 i번째 주소에 있는 phone_book의 문자열과 두번째 for문의 로컬 변수인 j번째 주소에 있는 phone_book의 문자열을 startsWith(String) 메서드로 교차하며 접두어가 있는지 확인하였다. 그 결과..! 값은 제대로 나왔지만 효율성 테스트 3, 4에서 시간 초과가 되었다...

🎯 startWith(String) : 매개변수로 받은 문자열이 메서드를 사용하는 문자열에 접두사로 존재하는지 확인하고 그 결과를 Boolean값으로 반환한다. ※endsWith(String)는 접미사를 확인한다.

그렇기 때문에 Hash를 통해 시간을 줄여서 풀어야 한다!!

두번째 풀이

💻 코드

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<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=1;j<phone_book[i].length();j++){
                if(map.containsKey(phone_book[i].substring(0, j))){
                    return false;
                }
            }
        }
        return true;
    }
}

📑 풀이 설명

이번에는 phone_book에 있는 값들을 HashMap에 옮기고 "첫번째 풀이"과 같이 이중 for문으로 접두사가 있는지 확인한다. 아까 String에 있는 메서드인 startsWith(String)을 사용했다면 이번에는 HashMap의 메서드인containsKey(Key)를 사용한다. 첫번째 for문의 i번째 주소에 있는 phone_book의 문자열의 길이만큼 두번째 for문을 실행하는데 이때 접두사를 확인하는 방법은 phone_book에 i번째 문자열을 자신의 길이-1만큼 잘라서 확인하게 된다. 이렇게 할 경우 자기 자신이 HashMap에 있다는건 확인하지 않고 뒤에 있는 문자열을 차례로 자르다가 HashMap 안에 잘린 문자열이 있으면 바로 false를 반환하게 되고 없으면 그대로 for문을 빠져나와 true를 반환하게 된다.

🎯 containsKey(Key) : 해당 Key가 Map에 존재하는지 Boolean 값으로 알려준다.
※ containsValue(Value)는 해당 Value가 Map에 존재하는지 Boolean 값으로 알려준다.
🎯 substring(start, end) : 문자열을 start와 end-1 만큼 자른다. 예를 들어 substring(0, 1)일 경우 문자열의 0번째 문자만 자르게 된다.`