[Hash] 전화번호 목록 - Java 풀이

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

코딩테스트 연습 - 전화번호 목록

 

문제

 

 

풀이 - HashSet 이용

import java.util.Arrays;
import java.util.HashSet;
public class 전화번호목록 {
	/*
	정확성  테스트
	테스트 1 〉	통과 (0.51ms, 70.5MB)
	테스트 2 〉	통과 (0.71ms, 72.7MB)
	테스트 3 〉	통과 (0.54ms, 73.1MB)
	테스트 4 〉	통과 (0.60ms, 74.1MB)
	테스트 5 〉	통과 (0.46ms, 76.2MB)
	테스트 6 〉	통과 (1.11ms, 87.9MB)
	테스트 7 〉	통과 (0.47ms, 71.9MB)
	테스트 8 〉	통과 (0.49ms, 71.4MB)
	테스트 9 〉	통과 (0.51ms, 75.4MB)
	테스트 10 〉	통과 (0.60ms, 77.6MB)
	테스트 11 〉	통과 (0.48ms, 77.4MB)
	테스트 12 〉	통과 (0.47ms, 77.6MB)
	테스트 13 〉	통과 (0.79ms, 70MB)
	테스트 14 〉	통과 (2.11ms, 76.7MB)
	테스트 15 〉	통과 (2.21ms, 68.6MB)
	테스트 16 〉	통과 (4.32ms, 79.8MB)
	테스트 17 〉	통과 (5.19ms, 78.1MB)
	테스트 18 〉	통과 (5.84ms, 79.1MB)
	테스트 19 〉	통과 (5.35ms, 80.8MB)
	테스트 20 〉	통과 (4.95ms, 87.9MB)
	효율성  테스트
	테스트 1 〉	통과 (9.24ms, 57.8MB)
	테스트 2 〉	통과 (4.53ms, 58MB)
	테스트 3 〉	통과 (326.45ms, 247MB)
	테스트 4 〉	통과 (372.85ms, 204MB)
	*/
	public static boolean solution(String[] phoneBook) {
        HashSet<String> set = new HashSet<>();
        Arrays.stream(phoneBook).forEach(s -> set.add(s));
        for(String str : set){
            for(int i = 1; i < str.length(); i++){
                if(set.contains(str.substring(0, i))){
                    return false;
                }
            }
        }
	    return true;
	}
	
	public static void main(String[] args) {
		String[] phoneBook = {"119", "97674223", "1195524421"};
		System.out.println(solution(phoneBook));
	}
}

 

모든 문자열을 1부터 잘라가면서 검사하는데, 자기 자신을 제외하면서 검사하도록 해보았다.

하지만 이보다 아래 정렬후 startwith을 사용한 코드가 더 간결하고 빠르다.

 

좋은 정답 코드

import java.util.Arrays;
/*
정확성  테스트
테스트 1 〉	통과 (0.44ms, 81.6MB)
테스트 2 〉	통과 (0.25ms, 74.3MB)
테스트 3 〉	통과 (0.33ms, 83MB)
테스트 4 〉	통과 (0.20ms, 75.1MB)
테스트 5 〉	통과 (0.34ms, 81.1MB)
테스트 6 〉	통과 (0.29ms, 71.7MB)
테스트 7 〉	통과 (0.38ms, 72.5MB)
테스트 8 〉	통과 (0.34ms, 85.9MB)
테스트 9 〉	통과 (0.20ms, 71.7MB)
테스트 10 〉	통과 (0.29ms, 76.4MB)
테스트 11 〉	통과 (0.28ms, 71.4MB)
테스트 12 〉	통과 (0.31ms, 87.9MB)
테스트 13 〉	통과 (0.29ms, 74.1MB)
테스트 14 〉	통과 (3.14ms, 81.3MB)
테스트 15 〉	통과 (3.90ms, 74.2MB)
테스트 16 〉	통과 (4.21ms, 86.8MB)
테스트 17 〉	통과 (5.92ms, 76.5MB)
테스트 18 〉	통과 (3.83ms, 78.2MB)
테스트 19 〉	통과 (3.73ms, 80.1MB)
테스트 20 〉	통과 (5.11ms, 79.6MB)
효율성  테스트
테스트 1 〉	통과 (30.23ms, 58.7MB)
테스트 2 〉	통과 (17.65ms, 58.6MB)
테스트 3 〉	통과 (309.08ms, 98.5MB)
테스트 4 〉	통과 (302.44ms, 97.1MB)
*/
class Solution {
    public boolean solution(String[] phone_book) {
        Arrays.sort(phone_book);
        for (int i = 0; i < phone_book.length - 1; i++) {
            if (phone_book[i + 1].startsWith(phone_book[i]))
	    	    return false;
        }
        return true;	
    }
}

이중 for문 없이,

정렬 후에 연속 되어 있는

그 다음 값들과 한번씩만 비교해주어도 어두가 포함되는지를 확인할 수 있다.