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

for문 2번 쓰고 naive 하게 찾으면 시간초과 발생

O(n^2)=백만 ^2 이기 때문

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

---

 

따라서 해쉬맵을 사용해야 함.

import java.util.HashMap;

class Solution {
    public boolean solution(String[] phone_book) {
       
        HashMap <String,Integer> map=new HashMap<>();
      
        
        for(int i=0;i<phone_book.length;i++){
            map.put(phone_book[i],i); //map에 전화번호 담기
        }
        
        for(int i=0;i<phone_book.length;i++){
            for(int j=1;j<phone_book[i].length();j++){ //번호 각각의 길이
                if(map.containsKey(phone_book[i].substring(0,j)))
                    //phone_book[i]를 한글자,두글자...씩 잘라서 map에 있는
                    //번호와 같은지 확인 -> 같다면 접두어가 존재하는 것.
                    return false;
            }
        }
        return true;
    }
}

 

 

containsValue()를 사용해 볼까 생각하고 해 봤지만 시간초과가 떴다.

 

map.contatinsKey()는 해당 Key값이 있는지 찾는 메서드이다.

Key값을 사용하여 해시 값을 계산하고, 이 값을 사용하여 해당 키가 있는지 빠르게 검색할 수 있다.

이는 상수 시간 복잡도인 O(1)을 가진다.

 

map.containsValue()는 해당 Value값이 있는지 찾는 메서드이다.

값에 대한 인덱스나 해시 값이 없으므로, HashMap에 있는 모든 요소를 검사해야 한다.

이는 선형 시간 복잡도인 O(n)을 가진다.

 

이런 이유로 시간초과가 발생했던 것이다.