99클럽 코테 스터디 5일차 TIL , 전화번호 목록

문제

풀이

번호가 또 다른 번호의 접두사가 되는 것이 있는지 찾는 문제.

예를 들면 "123"는  "123456"의 접두사이다. 

제출 1 - 실패

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        
        Arrays.sort(phone_book, new Comparator<>(){
           public int compare(String s1, String s2){
               if(s1.length() < s2.length()) return -1;
               else return 1;
           } 
        });
        
        for(int i=0;i<phone_book.length;i++){
            if(answer){
                for(int j=i+1;j<phone_book.length;j++){
                    if(phone_book[j].startsWith(phone_book[i])){
                        answer = false;
                        break;
                    }
                }
            }
        }
        
        
        return answer;
    }
}

 

전화번호부의 길이로 봤을 때 완전탐색으로 시간이 초과가 날 것으로 생각했지만, 풀이해 봤다.

길이를 기준으로 정렬하고 하나 지날 때 마다 모든 전화번호를 확인한다.

당연히 실패!

 

제출 2 - 정답

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])){
                answer = false;
                break;
            }
        }
        
        return answer;
    }
}

 

전화번호부를 사전순으로 정렬하면 만약 접두사 관계가 되는 게 존재할 시에 바로 앞에 접두사가 존재하게 된다.

예를 들어 "123456", "123", "123678"를 정렬하면 "123", "123456", "123678" 되고 바로 찾을 수 있게 된다.

 

TIL

• startsWith을 사용하여 간단하게 풀이 할 수 있었다.
• indexOf를 사용해서 0일 때 로직이 동작하게 풀이해도 맞는다.