[JAVA] Programmers <Hash_LV2> 전화번호 목록

전화번호 목록에 어떤 번호가 다른 번호의 앞부분에 모두 포함되는 경우를 찾아 false를 리턴하면 되는 간단한 문제이다. 처음엔 "이건 또 왜 Map을 써야하지?" 라는 생각이 들 정도의 간단한 문제인 줄 알아, 그대로 이중 for문을 이용하여 풀었다.

결과는...

 

아주 당연하게도 시간 초과....ㅎㅎ 테스트 케이스들이 100ms를 넘어갈 때부터 느낌이 쎄~ 하긴 했지만...처참했다.

그렇다면, Map을 사용하여 시간을 줄여야한다는 건데... 어떻게...?

고민 끝에 전화번호를 길이가 긴 순서대로 정렬하여 조각 조각 잘라 HashMap에 넣고, 넣기 전에 번호의 조각이 들어가 있는지, 없는지 확인하여 이미 들어간 조각이라면 바로 false를 반환하도록 설계하기로 했다.

 

우선 정렬은 Comparator클래스를 사용하여 길이 순으로 정렬했다.

 

Code:

 

Arrays.sort(phone_book, new Comparator<String>() {
	@Override
	public int compare(String o1, String o2) {
		return o2.length() - o1.length();
	}
});

이후에 다음과 같이 단어를 잘라 넣어주면서 넣기 전에 이미 들어가 있는 지 확인만 해주면 풀이는 끝이다.

 

Code:

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;

public class Solution {
	public boolean solution(String[] phone_book) {
		boolean answer = true;
		HashMap<String, String> wordMap = new HashMap<String , String>();
		Arrays.sort(phone_book, new Comparator<String>() {
			@Override
			public int compare(String o1, String o2) {
				return o2.length() - o1.length();
			}
		});
		for(String number : phone_book) {
			if(wordMap.get(number) != null)  return false;
			for(int i = 1, len = number.length(); i <= len; i++) {
				wordMap.put(number.substring(0,i),"On");
			}
		}
		return answer;
	}
}