hash - 전화번호 목록

첫 번째 풀이

public boolean solution(String[] phone_book) {
	HashSet<Object> hs = new HashSet<>();
		for (String s : phone_book) hs.add(s.subString(0,1));
	return hs.size() == phone_book.length;
}

중복된 값을 담지 않기 위해 HashSet을 이용하였다.

접두사가 앞에 한 글자인지, 두 글자인지 예시에는 두 글자라서 헷갈렸다..

위 코드 결과

• 정확성 41.7
• 효율성 12.5
• 합계 54.2

두 번째 풀이

효율성은 물론이고 왜 정확성도 떨어지나 생각을 해봤다.

이 문제에서 접두사의 정의는 어떤 배열의 값이 다른 배열의 값에 모든숫자가 일치할때 를 의미하는 것이었다...
다시 코딩해보자...

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

자 5분만에 다시 짰다.
단순하게 이중for문을 사용했기에 효율성은 떨어질 것이라고 예측하고 있었다.

하지만 이게뭐람. 정확성 TC 20개 중 3개도 실패를 했다(8,9,19)
효율성은 예측대로 4개중 반이 시간초과가 발생했다.

효율성은 나중에 생각하고 정확성부터 파보자.

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

자 깨달았다.
배열 앞 인덱스 값이 뒤 인덱스 값에 포함되는게 아니고 반대의 경우도 존재할 수 있으므로
OR 조건을 추가해서 정확성 테스트는 통과했다.

문제는 효율성이다

세 번째 풀이

public boolean solution(String[] phone_book) {
	HashMap<Integer, String> hm = new HashMap<>();
	Arrays.sort(phone_book); 

	for (int i = 0; i < phone_book.length; i++) 
    	hm.put(i, phone_book[i]);

	for (int i = 1; i < hm.size(); i++) 
    	if(hm.get(i).startsWith(hm.get(i-1))) return false;
    
	return true;

}

효율성도 해결했다.
그냥 단순하게 이중for문을 어떻게 안쓸 수 있을까 생각을 해봤다

위 풀이에서 이중for문을 썻던 이유는, 기준점을 잡고 모든 배열의 값을 비교하기 위해서이다.
이를 해결하기 위해 주어진 배열을 오름차순으로 정렬하여

1. 배열의 뒤에 값이 앞의 값을 포함하는지 단방향으로만 확인하면 된다.
2. 모든 인덱스의 값을 다 뒤져볼 필요가 없다.
3. 의도치않게 if문의 조건 또한 앞, 뒤 확인할 필요가 없어졌다.

이전 해시 문제도 그렇고 시간복잡도를 개선하여 효율성을 높이고 싶을경우에는 정렬에 의존하고 있는데
이렇게 계속 접근해도 괜찮은 건지 문제를 더풀어봐야 제대로 알 수 있을 것 같다.