[프로그래머스] 전화번호 목록 java /효율성 성공! Arrays.sort

ㅏ

 

나의 풀이

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) {
						continue;
					}
					if (phone_book[j].matches(phone_book[i]+"(.*)")) {
						answer=false;
					}
				}
			}
	        return answer;
    }
}

테스트 케이스는 통과했지만 효율성에서 모두 실패!

 

matches대신 

 if(phone_book[j].indexOf(phone_book[i])==0)

indexOf를 써도 케이스는 통과하지만 효율성에서 실패

import java.util.HashMap;
class Solution {
    public boolean solution(String[] phone_book) {
     boolean answer = true;

    	HashMap<String,String> map = new HashMap<String,String>();
    	
    	for(int i=0;i<phone_book.length;i++)
    		map.put(phone_book[i], phone_book[i]);
    	
    	for(int i=0;i<map.size();i++){
    		String a = map.get(phone_book[i]);
    		for(int j=i+1; j<map.size(); j++) {
    			if(a.startsWith(phone_book[j]) || phone_book[j].startsWith(a)) {
    				answer = false;
    				break;
    			}
    		}
    		
    		if(answer == false)
    			break;
    	
        }
        return answer;
}
}

HashMap을 썼지만 효율성 실패!

 

 

import java.util.Arrays;
public 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++) {
			if (phone_book[i+1].startsWith(phone_book[i])) {
				answer = false;
				break;
			}
		}
	       
	        return answer;
	    }
	}

Arrays.sort를 이용하여 정렬을 한다.

그렇게 정렬을 하면 요소의 길이는 고려하지 않고 숫자가 작은 것부터 정렬이 된다. 

이렇게 정렬이 된다.

그러면 어떤 문자를 접두사로 포함하는 문자는 그 접두사  바로 뒤의 인덱스에 위치하도록 정렬이 된다고 볼 수 있다.

그러므로 바로 뒤에것만 비교를 해주면 되겠다.