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

JoonYoung Maeng·2020년 12월 7일

🔗 문제 링크

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

🤔 문제

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

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

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

😮 문제 해결 방법

이 문제의 핵심은 주어진 phone_book 배열을 문자의 길이 순으로 정렬하는 것이라고 생각한다.

요소의 길이가 짧을수록 해당 요소를 제외한 나머지 요소의 접두어가 될 확률이 높다고 생각했기 때문이다.

예를 들어, {"78126", "245", "6789", "12543", "24"} 라는 배열이 주어지고, 요소의 길이 순으로 정렬한다면, {"24","245","6789","12543","78126"} 순으로 정렬된다.

그렇다면 "24" 가 for문을 한번 돌고 "245" 의 접두어이므로 바로 false 를 return 하면서 종료한다.

요소를 길이 순으로 정렬했다면, 이제 요소를 돌면서 접두어인지 확인하고 return 해주면 문제가 해결된다.

아래는 Java로 구현한 코드이다.

🚩 JAVA 코드

package com.algorithm.Programmers.Lv2;

import java.util.Arrays;
import java.util.Comparator;

public class Solution_42577 {
    public static void main(String[] args) {
        String[] phone_book ={"2","23","454545","123", "1195524421","119"};
        System.out.println(solution(phone_book));
    }
    public static boolean solution(String[] phone_book) {
        boolean answer = true;

        // Comparator를 통해 배열 길이 순으로 오름차순 정렬
        Comparator<String> comparator = new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return Integer.compare(o1.length(),o2.length());
            }
        };
        Arrays.sort(phone_book,comparator);

        for(int i=0;i< phone_book.length;i++){
            for(int j=i+1;j< phone_book.length;j++){
                if(phone_book[j].startsWith(phone_book[i])){
                    answer = false;
                    // break을 쓰면 for문 하나만 탈출 하므로 return
                    // 효율성 문제 해결
                    return answer;
                }
            }
        }
        return answer;
    }
}