프로그래머스_해시_전화번호 목록 (JAVA)

 

문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 입출력 예제입출력 예 설명 입출력 예 #1 앞에서 설명한 예와 같습니다. 입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다. 입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

 

 

다른 사람들 코드를 보니 해시를 사용하지 않고 푼게 대부분인 것 같습니다. 사실 단순한 문제라 굳이 해시 없이도 풀 수 있지만 이 문제의 카테고리는 해시이고 다른 문제를 풀기 위한 연습문제인만큼 해시를 사용하는게 맞다고 생각합니다.

 

문제의 핵심은 다른 해시 문제들과 마찬가지로 "다량의 반복적인 문자열 비교가 필요하다"입니다. 문자열을 비교하는 가장 빠른 방법중의 하나가 Hash 기법이고, 그냥 쌩으로 equals()나 startWith()를 사용하는 것은 노가다 문자열 비교입니다. 제가 알기로 해당 메소드에 해싱 기법이 들어가지는 않는 것으로 알고 있습니다. 알고리즘에서 문제에서 "노가다 문자열 비교 작업"이 필요하다면 해시를 먼저 떠올리는 것이 좋을 듯합니다.

 

아래는 String 클래스의 startsWith() 구현식입니다. equals()와 같이 char 타입의 배열로 만들어 값을 반복문으로 확인하는 것을 알 수 있습니다.

    public boolean startsWith(String prefix, int toffset) {
        char ta[] = value;
        int to = toffset;
        char pa[] = prefix.value;
        int po = 0;
        int pc = prefix.value.length;
        // Note: toffset might be near -1>>>1.
        if ((toffset < 0) || (toffset > value.length - pc)) {
            return false;
        }
        while (--pc >= 0) {
            if (ta[to++] != pa[po++]) {
                return false;
            }
        }
        return true;
    }

 

 

---

 

 

해시 방식을 통한 비교는 문자열을 하나의 해시코드 숫자로 만든 뒤 두 숫자를 비교합니다. 일단 기준점이 되는 문자열은 한 번 해시코드로 변환되면 이후 문자열 자체가 필요 없어지고, 비교 대상이 되는 문자열은 해시코드로 먼저 변환한 뒤 기준 문자열의 해시코드와 숫자가 같은지 다른지만 체크하면 됩니다.

 

아래는 제 스타일로 짠 코드입니다. HashSet을 써도 되고 반복문을 돌리는 방식도 여러 가지가 있을 것 같습니다. 

 

package pojoPrj;

public class Solution {

	public static Boolean solution(String[] phone_book) {

		for (int i = 0; i < phone_book.length - 1; i++) {

			int hashPhone = phone_book[i].hashCode();
			int len = phone_book[i].length();

			for (int j = i + 1; j < phone_book.length; j++) {

				if (phone_book[j].length() >= len
						&& hashPhone == (phone_book[j].substring(0, len).hashCode())) {
					return false;

				} else if (phone_book[j].length() < len
						&& phone_book[i].substring(0, phone_book[j].length())
								.hashCode() == phone_book[j].hashCode()) {
					return false;
				}

			}
		}

		return true;
	}
}

 

 

---

 

 

아래는 인터넷에서 가장 많이 보이는 답안입니다. 궁금해서 결과를 측정해봤는데 속도는 비슷하게 나옵니다. 이 문제에서는 문자열 길이가 워낙 짧기도 하고, 라빈 카프 알고리즘과 같이 해싱을 통해 중복 연산을 제거해줄 부분이 없어서 그런 것 같습니다.

 

사실 지금처럼 유동적으로 계속 새로운 해시값을 만들어가며 비교하는 방식은 해시의 강점을 살리기는 좀 힘들어보이긴 합니다. 또 HashMap은 단순히 해시값을 매칭해 찾는게 아니라 내부적인 기준으로 분류를 해둡니다. 마치 여러개의 서랍이 있어서 숫자 크기 기준 10개 단위로 한 서랍씩 넣어두는 것과 같습니다. 그만큼 검색 속도가 빨라집니다. 지금 로직에서는 이런 해시 방식의 장점을 살릴 수 있는 부분이 거의 없어서 속도 차이가 나지 않네요. 

 

아무리봐도 해싱을 통한 중복연산 제거가 들어갈 부분이 없어보이는데 이 문제가 왜 해시 카테고리에 있는지는 좀 더 연구를 해봐야 알 것 같습니다.  

 

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;
    }
}

 

 

---

 

 

오름차순 정렬을 먼저 한 뒤 앞뒤로 비교하는 방법도 있습니다. 하지만 문자열 정렬에 드는 시간과 연산작업이 만만치 않기 때문에 테스트를 해보면 2중 반복문이 있는 코드들보다 시간이 더 오래 걸리는 것으로 측정됩니다. 문자열 비교에 해싱을 사용해도 비슷하게 나옵니다.

 

정렬의 경우 시간복잡도 자체는 nlog(N)이라 정렬 후 단일 반복문만 수행하면 2중 반복문(N^N)보다 시간복잡도가 작아보이지만, 값을 계속 바꿔주는 작업이 추가로 수행되므로 단순히 루프를 돌며 값을 체크하는 것보다 오래걸릴 수 있습니다.

 

import java.util.Arrays;

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;
    }
}