링크

전화번호 목록

문제설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

• 구조대 : 119
• 박준영 : 97 674 223
• 지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한사항

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

풀이 1

2가지로 풀어보았다.
우선, hash를 쓰지 않고 1중 for문으로 풀었다. 처음에는 2중포문으로 풀었는데 phone_book의 길이가 최대 1,000,000이하이기에 효율성에서 에러가 떴다. 그렇기에 phone_book을 정렬한 다음

for(int i=0; i<phone_book.length-1; i++)
        {
            if(phone_book[i+1].startsWith(phone_book[i]))
                return false;

그러면 사전 순으로 정렬이 되기에 바로 앞에 부분이랑 비교만 하면 끝

Code 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-1; i++)
        {
            if(phone_book[i+1].startsWith(phone_book[i]))
                return false;
        }
        return answer;
    }
}

풀이 2

두번째 풀이는 hashmap의 관점으로 풀 수 있다.
우선 가지고 있는 phone_book을 key값으로 넣는다. 여기서 그 값의 접두사만 필요하기에 value는 어떤 값을 넣어도 상관없다.

이제 여기서 그 값의 phone_book[i].substring(0, j)를 사용한다면 각각의 접두사가 존재하냐만 판단하면 된다!

Code 2

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        HashMap<String, Integer> hm=new HashMap<String, Integer>();
        boolean answer = true;
        
        for(int i=0; i<phone_book.length; i++)
            hm.put(phone_book[i], i);
        
        for(int i=0; i<phone_book.length; i++)
        {
            for(int j=0; j<phone_book[i].length(); j++)
            {
                if(hm.containsKey(phone_book[i].substring(0,j)))
                {
                    return false;
                }
            }
        }
        return answer;
    }
}