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

첫번째 시도

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        
        Arrays.sort(phone_book);
        for (int i=0;i<phone_book.length;i++) {
            String cur = phone_book[i];
                 if (phone_book[j].startsWith(cur)) {
                     return false;
                 
             }
        }
        
        return true;
    }
}

사실 phone_book이 1,000,000이하로 되어 있어 시간 초과가 당연한 결과였다.(정확성은 통과하지만 효율성에서 통과를 못한다) (보면 시간복잡도가 n2이다)

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        
        Map<String,Integer> map = new HashMap<>();
        
        for (int i=0;i<phone_book.length;i++) {
            map.put(phone_book[i],i);
        }
        
        for (int i=0;i<phone_book.length;i++) {
           for (int j=0;j<phone_book[i].length();j++) {
               if (map.containsKey(phone_book[i].substring(0,j)))
                   return false;
           }
        }
        
        return true;
    }
}

결국 못 풀어서 다른 분들의 풀이를 참조하였다. 말 그대로 해시를 이용하여 푸는 방법으로 각 값을 map에 key로 넣고 이후 한 단어씩 가져오는데 비교 할 때를 보면 한 글자씩 늘려가며 비교한다.

출처: 프로그래머스 알고리즘 https://school.programmers.co.kr/learn/courses/30/lessons/42577