[코딩테스트 연습, 프로그래머스, Java] - 전화번호 목록

💡문제 설명

 

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.

• 전화번호부에 적힌 전화번호 중 한 번호가 다른 번호의 접두어인 경우가 있는지 확인.
• 접두어이면 false, 아니면 true

💡제한 사항

• phone_book의 길이는 1 이상 1,000,000 이하입니다.
• 각 전화번호의 길이는 1 이상 20 이하입니다.
• 같은 전화번호가 중복해서 들어있지 않습니다.

💡문제 단순화하기

하나라도 접두어냐?

한 번호가 다른 번호의 접두어라면 false, 아니면 true.

 

💡풀이

 

1. Sorting/Loop를 활용한 solution

• 전화번호를 오름차순으로 sorting(정렬)한다.
• 한 번의 루프만 돌면서 두 개의 숫자를 비교한다.
• 앞의 숫자가 뒤의 숫자의 접두어인지 확인하면 접두어를 구할 수 있다.

import java.util.Arrays;

class Solution {
    public boolean solution(String[] phone_book) {
    	
    	//1. phone_book을 정렬한다.
    	Arrays.sort(phone_book);
    	
    	//2. 1중 loop를 돌면서 앞번호가 뒷번호의 접두어인지 확인한다.
    	for(int i=0; i<phone_book.length-1; i++)
    		if(phone_book[i+1].startsWith(phone_book[i]))
    			return false;
    	
    	//3. 여기까지 오지 못했다면 접두어가 없다는 것이다.
        return true; //접두어가 없을 경우 true리턴
    }
}

 

2. Hash를 활용한 solution

• Key = phone_number / Value = 1을 갖는 HashMap을 만들어준다.
• 각 번호의 접두어가 HashMap에 존재하는지 확인한다.
• 접두어를 찾아야 하기 때문에, 기존 전화번호와 같은 수를 HashMap에서 찾으면 안 된다.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
    	
    	//1.HashMap을 만든다.
    	HashMap<String, Integer> map = new HashMap<>();
    	for(int i=0;i<phone_book.length;i++)
    		map.put(phone_book[i], 1);
    	
    	//2.모든 전화번호의 접두어가 HashMap에 있는지 확인한다.
    	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;
    	
    	//3.여기까지 왔다면 접두어가 엇ㅂ다는 것이다.
    	return true;
    	
    }
}