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

코딩테스트 연습 - 전화번호 목록 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 전화번호 목록

어떻게 생각하고 문제를 풀었는가?

특정 원소가 다른 원소의 접미사인지 확인하기 위해 주어진 원소들을 먼저 저장하고, 각 원소들의 가능한 접미사가 저장한 원소에 해당한다면 false를 반환하는 방식으로 문제를 해결할 수 있을 것이라고 생각하였습니다.

 

코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        Set<String> set = new HashSet<>();
        for (String s : phone_book) set.add(s);
        
        for (String s : phone_book)
            for (int i = 0; i < s.length(); i++)
                if (set.contains(s.substring(0, i)))	return false;
        return true;
    }
}

중복을 허용하지 않는 컬렉션 HashSet에 문자열들을 먼저 저장하고, 각 문자열들을 substring으로 접미사들을 만들어 검사하는 방법으로 테스트를 통과하였습니다. 

생성한 접미사가 HashSet에 포함되어 있는경우 다른 검사를 수행할 필요 없이 false를 반환, 모든 검사를 수행하였을 때 false가 리턴되지 않으면 true를 반환합니다.

개선

import java.util.*;
class Solution {
    public boolean solution(String[] phone_book) {
        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 true;
    }
}

 

String의 startsWith함수는 접미사를 검사하는 함수입니다. 해당 함수를 사용하여 문자열이 접미사인지 확인할 수 있습니다.

문자열들을 사전순으로 정렬하였을 때 같은 접미사에서 길이가 더 긴 문자열이 순서가 뒤에 있습니다.

앞의 문자가 순서상 뒤의 문자열에 접미사로 포함되는지 확인함으로서 검사 횟수를 줄일 수 있고, 접미사가 다르다면 이후 문자열들도 접미사가 다름을 의미하므로 앞의 문자열과 뒤의 문자열만 검사하여 결과를 찾을 수 있습니다.