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

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

코딩테스트 연습 - 전화번호 목록 | 프로그래머스

코드

class Solution {
    	public boolean solution(String[] phone_book) {
		boolean answer = true;
		boolean flag = true;
		for(int i=0; i<phone_book.length; i++) {
			for(int j=0; j<phone_book.length; j++) {
				// 한 번호가 다른 번호의 접두어인 경우
				if(i!=j && phone_book[j].startsWith(phone_book[i])) {
					answer = false;
					flag = false;
					break;
				}
			}
			if(!flag)
				break;
		}
		return answer;
	}

}

풀이

phone_book의 모든 요소들을 탐색한다.

starsWith() 메소드는 대상 문자열이 특정 문자 또는 문자열로 시작하는지 체크하는 함수다.

 

접두사가 하나만 있어도 false를 리턴하면 되므로, 시간적으로 단축시키기 위해 flag 변수를 선언했는데,

만약 한 번호가 다른 번호의 접두어인 경우 => 다음부터는 찾을 필요도 없으므로 for문을 모두 탈출한다.

 

 

생각

phone_book 의 범위는 1,000,000 이하이다.

그래서 완전탐색을 돌리면 O(1,000,000 * 1,000,000) 으로 시간초과가 발생할 줄 알고 해봤는데,, 효율성에서 통과를 해서 좀 놀랐다.

테스트 케이스가 100만번 전부 도는 케이스가 없어서인지, 아니면 프로그래머스가 시간(?)쪽에서 후해서 인지는 잘 모르겠다 . .

 

 

 

다른 풀이

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

나도 처음에는 두 번째 for문을 j = i+1부터 돌려봤지만, 테스트 케이스에서 틀리다고 나왔다. 반례가 존재했다.

만약 phone_book 의 요소가 ["1237" , "45" , "123"] 일 경우, 

두 번째 for문을 j=i+1부터 돌리게 되면, 123이 1237의 접두어지만, 검사를 하지 못하게 된다.

따라서 위 코드처럼 i, j 둘다 반복하게 된다면 정답으로 처리가 된다.

 

위에서 두 번 검색하는것이 for문 전부를 탐색하는 것보다 효율성 테스트에서도 시간이 짧다.

6.63ms => 0.86ms

거의 8배 가량 감소한다.

해시 문제지만, 해시 문제가 아닌(?) 문제다 . .