[programmers] 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

문제

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

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

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

제한 사항

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

입출력 예제

phone_bookreturn

["119", "97674223", "1195524421"]	false
["123","456","789"]	true
["12","123","1235","567","88"]	false

입출력 예 설명

입출력 예 #1
앞에서 설명한 예와 같습니다.

입출력 예 #2
한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3
첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

발상

정렬을 하면 앞뒤 비교만으로 간단하게 해결될 것 같아서 정렬 후 순서대로 하나의 문자열을 그 다음 문자열이 포함하고 잇는지 여부를 검사하는 방식으로 접근하였다.

의사코드

1. 입력값 정렬
2. 배열수+1 만큼 반복{
	1. 다음 배열의 값이 현재 배열의 값을 가지고 있으면 false
}
3. true 리턴

 

코드

        if (phone_book.length == 1) return true;
        Arrays.sort(phone_book);
        for (int i = 0; i < phone_book.length - 1; i++) {
            String pattern = "^"+phone_book[i]+".*";
            if(phone_book[i+1].matches(pattern)) return false;
//            if(phone_book[i+1].contains(phone_book[i])) return false;
//            if (phone_book[i].length() <= phone_book[i + 1].length() && phone_book[i].equals(phone_book[i + 1].substring(0, phone_book[i].length())))
//                return false;
//            for (int j = i+1; j < phone_book.length; j++) {
//                if (phone_book[j].contains(phone_book[i])) {
//                    return false;
//                }
//            }
        }
        return true;
    }

개선

처음엔 contains로 접근하였는데, 테스트케이스를 통과하지 못하는 예외케이스가 발생하였다.

생각해보니 제시된 문자열로 시작하는 경우만 검사해야 하기 때문에, substring으로 수정하여 통과시켰다가

다시 정규식으로 전환하였는데, 정규식은 패턴문자열을 계속해서 만들어야 하다 보니까 성능이 훨씬 안나왔다.