문제 설명

문자열로 구성된 전화번호 부 배열이 주어졌을 때 전화번호 부 내에 문자열이 다른 문자열의 접두어가 같은 문자열이 하나라도 있으면 false를 리턴하고 아니면 true를 반환해주도록 구현하는 문제이다.

• 제한 사항
  • phone_book의 길이는 1 ~ 1,000,000 이하
    • 전화번호의 길이는 1 ~ 20
    • 중복된 전화번호는 없다.

문제 링크 : 전화번호 목록

풀이

주어진 phone_book 배열의 크기가 최대 1,000,000이기 때문에 이중포문으로 문자열을 비교하면 최악의 경우 시간초과가 발생한다. 따라서 최대한 가장 큰 값인 phone_book 배열(1,000,000) 반복을 줄여야 하는 문제이다.

그렇기 때문에 set에 각 문자열을 담고 이후에 문자열 배열을 전부 순회하면서 문자열이 최대 20까지라서 1부터 20까지 부분 문자열을 뽑아서 set에 조회하여 존재한다면 바로 종료한다.

다른 풀이를 보니 문자열이 중복되지 않아서 sort를 통해 오름차순을 하여 가장 짧은 단어가 앞으로 오게해서 앞에서부터 순회하며 조회하는 방법이 있었다. 그리고 접두사 찾기라서 startsWith() 를 사용할 수도 있었다.

코드

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        HashSet<String> set = new HashSet();
        for(int i=0;i<phone_book.length;i++) {
            set.add(phone_book[i]);
        }
        start:for(int i=0;i<phone_book.length;i++) {
            for(int j=0;j<phone_book[i].length();j++) {
                if (set.contains(phone_book[i].substring(0, j))) {
                    answer = false;
                    break start;
                }
            }   
        }  
        return answer;
    }
}