[알고리즘] 전화번호 목록 문제

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

프로그래머스

 

취준 중 오랜만에 여유가 생겨서 알고리즘 문제를 하나 풀어봤다!

 

전화번호부에 있는 번호들 중, 어떤 번호가 다른 번호의 접두어인지 확인하는 문제.

전화번호는 최대 1,000,000개.
길이는 각각 최대 20.

 

이중 for문으로 모든 번호를 다 비교하면 O(N²)인데,
최악의 경우 10^12번 비교해야 해서 말이 안 됨.
보통 1초에 10^8번 연산 가능하다고 잡으면 10,000초 수준이라 사실상 불가능.

따라서 이중 for문은 아님.

 

그럼 어떤 자료구조를 쓰면 좋을까?

처음에는 hash도 생각났는데,
이 문제는 단순 조회가 아니라 문자열끼리 접두어 비교가 필요해서
순서가 없는 map보다는 정렬 후 비교할 수 있는 list가 더 낫다고 판단.

 

일단 리스트로 바꾼 뒤 sort 해봄.
String 정렬 기준이 정확히 헷갈려서 직접 출력해봤는데,
사전순으로 잘 정렬되고 접두어 후보들도 서로 붙게 됨.

 

그러면 굳이 모든 문자열을 다 비교할 필요 없이
정렬된 상태에서 인접한 두 개만 비교하면 됨.

 

즉, curr와 next를 비교해서
next.startsWith(curr) 이면 curr가 next의 접두어라는 뜻이므로 false 반환.

 

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        
        List<String> arrList = Arrays.asList(phone_book);
        
        Collections.sort(arrList);
        
        for(int i = 0; i < arrList.size() -1; i++){
            String curr = arrList.get(i);
            String next = arrList.get(i+1);
            
            if(next.startsWith(curr)){
                return false;
            }
        }
        
        return true;
    }
}