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

전화번호 목록

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false, 그렇지 않을 경우 true를 반환

 

■ 문제 풀이

- 첫 번째 solution에서는 전화번호부를 sorting을 한 후 for문을 사용해서 앞의 번호가 뒷 번호의 접두어인지를 확인 
- 두번째 solution에서는 전화번호의 모든 번호를 hashSet에 넣은 후 전화번호부 배열을 for문으로 순차적으로 접근해서 접두어의 길이만큼 substring 하여 탐색을 시작한다.

[특정 문자로 시작하거나 끝나는지 체크]
1) String 클래스의 startWith() 
- boolean startWith(String prefix)
- 대상 문자열이 특정 문자 또는 문자열로 시작하는지를 체크

2) String 클래스의 endWith()
- boolean endWith(String suffix)
- 대상 문자열이 특정 문자 또는 문자열로 끝나는지 체크

 

import java.util.Arrays;
import java.util.HashSet;

public class ListOfPhoneNum {

    /**
     * 첫번째 solution에서는 이중 loop를 사용한 것이다 -> 효율적이지 못하다
     */
    static boolean solution(String[] phone_book) {
        //1. phone_book을 sorting
        Arrays.sort(phone_book);

        /**
         * String 클래스의 startsWith() 이용
         */
        //2. 앞의 번호가 뒷 번호의 접두어인지 확인
        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i])) {
                return false;
            }
        }
        return true;
    }

    /**
     * Hash를 사용
     * phoneBook의 모든 번호를 Hasing 해놓고, 접두어를 찾는 방식으로 문제 풀이
     */
    static boolean solution2(String[] phone_book) {
        HashSet<String> set = new HashSet<>();
        for (String phoneNum : phone_book) {
            set.add(phoneNum);
        }

        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;
    }

    public static void main(String[] args) {
        /**
         * test case 1.
         * return false
         */
        String[] phone_book = {"119", "97674223", "1195524421"};

        /**
         * test case 2.
         * return false
         */
        //String[] phone_book = {"12", "123", "1235", "567", "88"};

        /**
         * test case 3.
         * return true
         */
        //String[] phone_book = {"123", "456", "789"};

        boolean answer = solution(phone_book);
        System.out.println("answer = " + answer);
    }
}