[Hash] 프로그래머스 전화번호 목록 문제풀이 Java

• 전화번호 목록

• https://programmers.co.kr/learn/courses/30/lessons/42577?language=java

 

문제 설명

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

• 구조대 : 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입니다.

 

해설.

 

가장 직관적인 풀이를 보여준다. 아마 C같은 다른 언어에 익숙하면 다 이렇게 풀었을 것이다.

import java.util.HashSet;
class Solution {
     public boolean solution(String[] phone_book) {
        for(String i : phone_book){
            for(String j : phone_book){
                if(!i.equals(j) && i.length() < j.length()&& i.equals(j.substring(0,i.length()))) return false ;
            }
        }
        return true;
    }
}

하지만 보면 알겠지만, 이중 포문 사용에 의해 O(n^2)의 시간 복잡도를 갖는다.

 

비교 알고리즘은 counting sort 혹은 radix sort 아니면 최소 O(nlogn)의 시간 복잡도를 갖을 수밖에 없고.

비교 하면 가장 쉽게 생각할 수 있는 것이 곧 정렬이다.

 

 

최적의 비교는 집합을 절반으로 나누는 경우이다.

참조 : 스털링 근사 https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%84%B8%EB%A7%81_%EA%B7%BC%EC%82%AC 

스털링 근사 - 위키백과, 우리 모두의 백과사전

비교 문제라면 일단 정렬을 할 수 있는가? 를 생각하면 중간 이상은 간다.

왜냐하면 nlogn의 시간 복잡도는 곧 비교의 가장 효율적인 복잡도나 마찬가지이기 때문이다.

 

nlogn 정렬은 퀵소트와 merge sort가 있다는 것도 기억하자.

 

그렇다면 이 경우는 어떻게 해결하는 것이 가장 효율적일까? 내 생각엔 밑에 풀이가 가장 좋지 않을까 생각한다.

String을 정렬하면 Alpabetical Order로 가장 근사한 것들 끼리 붙어있기 때문에, 사용 가능한 idea다.

 

import java.util.Arrays;
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;
    }
}

자바에는 신박하게도 startsWith라는 함수가 존재한다. 맨 위의 풀이와 로직은 동일할 것이다.

 

이 풀이는 nlogn이다. 이유는 효율적인 sort를 사용하였고,

밑의 for문이 시간복잡도가 n이기 때문이다.

 

항상 공간복잡도와 시간복잡도를 생각해보자.

 

코딩 테스트에서는 공간복잡도보다는 시간복잡도를 더 중요시 여기는 경우가 많으니

 

1. 일단 풀어보고

2. 이게 최선인가

 

를 계속해서 생각해보자.