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

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

프로그래머스

 

1,5, 13, 14 실패

- contains 메서드는 접두사에 올바른 결과를 줄 수 없음

// 1,5, 13, 14 실패
import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
       
    for (var a: phone_book)
	    for (var b: phone_book)
    	    if (a != b && a.contains(b))
        	    return false;

    
    return true;
        
    }
}

 

 

효율성 에러 2번, 3번 난 코드

- 접두사에는 적합하지만 효율적이지 못함

코드 실행시 startsWith 메서드 최악의 경우 O(m)

전체 시간 복잡성은 O(n^2 * m)이 될 수 있음

//효율성 2,3 에러남
for (var a: phone_number)
	for (var b: phone_number)
    	if (a != b && a.startsWith(b))
        	return false;

 

 

 

 

 

 

HashMap과 substring을 이용하여 푼 코드

import java.util.*;

class Solution {
    public boolean solution(String[] phone_book) {
        HashMap <String, Integer> map = new HashMap<String,Integer>();
    
        for (var num: phone_book){
            map.put(num,0);
        }
        
        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;
        
    }
}

 

 

• 첫 번째 반복문: 각 전화번호를 해시맵에 저장 (O(n))
• 두 번째 반복문: 각 전화번호의 접두사를 확인 (O(n * m))

여기서 n은 전화번호의 개수이고 m은 각 전화번호의 평균 길이

해시맵 조회는 평균적으로 O(1)이므로 전체 시간 복잡성은 O(n * m)