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

첫 시도

• 입력받은 값을 key로 하여 map 생성
• 입력 값의 서브스트링 길이를 늘려가면서 map에 서브스트링과 동일한 키가 있는지 반복
• phone_book배열의 길이를 N, 각 전화번호의 길이를 M이라고 했을때 시간 복잡도는 O(NM)이다 -> 10^6 * 2 * 10

해결

import java.util.*;

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

참고

• https://hyojun.tistory.com/entry/Programmers-%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8-%EB%AA%A9%EB%A1%9D-Javap