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

Problem

• 문제 링크

전화번호 리스트가 주어지면 한 번호가 다른 번호의 접두어가 되는 경우가 있는지 확인하는 문제입니다.

 

예를 들어 ["119", "119231"] 이 있으면 "119" 는 "119231" 의 접두어가 되기 때문에 false 가 됩니다.

 

카테고리는 해시로 분류되어있는데 해시를 써도 되고 안써도 됩니다.

 

 

Solution 1

첫번째 풀이는 HashSet 을 사용했습니다.

 

일치하는 문제를 찾는게 아니기때문에 HashSet.contains() 을 사용하지는 못하고 Set 을 순회하며 startsWith 으로 비교하였습니다.

 

 

Java Code 1

import java.util.*;

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

        for (String phone : phone_book) {
            for (String s : set) {
                if (phone.startsWith(s) || s.startsWith(phone))
                    return false;
            }

            set.add(phone);
        }

        return true;
    }
}

 

 

Solution 2

두번재 풀이는 String 정렬의 특징을 이용하였습니다.

 

String 은 정렬하면 사전순으로 정렬되기 때문에 ["1", "2", "11"] 을 정렬하면 ["1", "11", "2"] 가 됩니다.

 

따라서 무조건 앞의 변수만 비교하면 되기 때문에 for 문 한번으로 끝낼 수 있습니다.

 

하지만 정렬하는 비용이 들기 때문에 효율성 테스트에서는 Solution 1 보다 비효율적이었습니다.

 

 

Java Code 2

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        
        String beforePhone = "dummy";
        for (String phone : phone_book) {
            if (phone.startsWith(beforePhone))
                return false;
            
            beforePhone = phone;
        }
        
        return true;
    }
}