[프로그래머스/JAVA] 전화번호 목록 - 해시

 

 

먼저 배열의 데이터 하나하나를 다 비교하는 단순한 방법으로 풀어보았다.  역시나 효율성 테스트에서 탈락!  이렇게 풀지 말라고  기록해본다..

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

 

import java.util.Arrays;

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

먼저 phone_book을 sorting했는데도 또 효율성 테스트 3, 4에서 걸려버리고 말았다.

hash를 사용하지 않고 먼저 풀어보고 싶었는데.. hash로 풀어야하나 보다.

 

import java.util.HashMap;

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

 HashMap에  전화번호를 put하고, 각 전화번호를 전화번호 길이까지 하나씩 증가시키면서 잘랐을 때 그 값을 키로 가지는것이 HashMap에 있으면 false를 출력한다. 없으면 true 출력!