[JAVA] 프로그래머스 42577 전화번호 목록

 

 

 

첫번째 시도 : 삼중포문......... 

 

삼중포문이라 시간초과가 날 게 뻔했지만 일단 질러본,, 풀이 

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = true;
        

        for(int i=0; i<phone_book.length-1; i++){
            for(int j=i+1; j<phone_book.length; j++){
                int sho = phone_book[i].length() < phone_book[j].length() ? phone_book[i].length() : phone_book[j].length();

                for(int k=0; k<sho; k++){
                    if(phone_book[i].charAt(k)!=phone_book[j].charAt(k)){
                        break;
                    }
                    else {
                        if(k==sho-1) answer=false;
                    }
                }

            }
        }
        
        return answer;
    }
}

 

 

역시나 시간초과,,,,

정확성은 다 통과지만 효율성 다 탈락 

 

 

 

 

 

두 번째 시도 : 문자열 함수 이용하기 

 

문자열이 특정 문자열을 포함하는지 확인하는 contains()는 접두사문제에 적용이 안된다. 

특정 문자열이 접두사에 해당하는지 알 수 있는 startsWith() 함수를 알게 되었다! 

 

class Solution {
    public boolean solution(String[] phone_book) {
        boolean answer = false;
        

        for(int i=0; i<phone_book.length-1; i++){
            if(answer) break;
            for(int j=i+1; j<phone_book.length; j++){
                if(answer) break;
                boolean sho = phone_book[i].length()< phone_book[j].length();
                if(sho){
                    answer = phone_book[j].startsWith(phone_book[i]);
                }else{
                    answer = phone_book[i].startsWith(phone_book[j]);
                }

            }
        }
        return !answer;
    }
}

 

효율성 테스트에서 반절 탈락..

 

 

 

 

 

세 번째 시도 : 정렬을 하자!

 

아무래도 해시 알고리즘에 딸린 문제다 보니까 해시 알고리즘을 써야할 것 같아서 쓸만한 메소드가 있는지 알아보던 중에

정렬된 순서대로 키-값 쌍을 저장하는 TreeMap을 알게 됐다! 아 정렬을 하면 위 코드 처럼 하나하나 다 비교하는게 아니라 적어도 앞이 같거나 비슷한 애들끼리만 비교하면 되겠구나

 

만약 번호가 [ "119", 1234", "119017" ] 이라면 정렬한 다음 ["119", "119017", "1234"] [i+1]번째 숫자가 [i]번째로 시작하는지 startsWith()함수를 쓰면 될 것 같다. 

 

import java.util.Arrays;

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;
    }
}

 

깔끔하게 성공!!

 

 

 

🙄 이번 문제를 풀면서 알게된 것 

 

- 정렬된 상태로 저장하는 MAP인 TreeMap이 있다. 

- 접두어인지 확인할 수 있는 startsWith() 문자열 관련 함수가 있다. 

 

++ 자바 컬랙션 프레임워크에 대해 공부해서 정리해봐야겠다.