[Hash, 난이도 중] 프로그래머즈, 전화번호 목록

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성하는 문제이다.

 

여기서 제한 사항을 보면 phone_book의 길이는 1 이상 1,000,000 이하이고 각 전화번호의 길이는 1 이상 20 이하이다.

phone_book의 길이를 N, 전화번호의 최대 길이를 E이라고 하자.

해쉬를 안쓰고 전화번호 자리수까지 일일이 매칭한다면 시간 복잡도는 O(N^2*E) 까지도 나올 것이다.

아무리 해쉬를 쓴다고 해도, 접두어의 여부를 확인하기 위해 전화번호들을 모두 하나씩 매칭하는 방법을 쓰려면 시간 복잡도가 O(N^2) 이 나오므로 효율성은 매우 안좋다.

 

그렇다고 전화번호의 길이는 최대 20이므로, 전화번호부 문자열 자체를 정수로 치환하는것은 정수 범위가 어마어마해지기 때문에 좋은 방법이 아니다.

 

이제 내 접근법을 소개할 것이다.

시간복잡도가 O(E*NlogN) 인 접근법이다.

phone_book 문자열 벡터를 오름차순으로 정렬하면 대폭 작은 시간복잡도로 문제를 해결할 수 있을 거라는 생각이 들었다. 물론 정렬은 시간복잡도가 O(NlogN)인 퀵정렬을 사용했다.

그러면 문자열의 첫 문자부터 으로 깔끔하게 정렬되기 때문에 바로 옆에 있는 문자열끼리 비교했을 때, 접두어 판별이 매우 쉬워진다는 것이다. 

추가로 pair을 이용하여 전화번호 문자열에 대한 해시값까지 전화번호와 같이 push 했다.

접두어 판별을 더 쉽게 하기위해 해시값을 같이 붙인 것이다.

 

예를 들어 정렬 후의 문자열벡터에서 인접한 두 문자열을 373653, 373653999 라고 가정하자.

물론 눈으로 보면 접두어인 것이 딱 보일 것인데 이제 컴퓨터에게도 판별할 수 있게 해주면 된다.

해시 값은 각 문자의 아스키 코드와 2^(19-index)의 곱을 더하여 부여했다.

 

그렇다면 373653와 373653999중 문자열의 길이가 더 긴 것은 후자이므로

문자열의 길이를 맞추기 위해 373653999 에서 "999" 부분에 계산되었던 해시값을 빼면 373653의 해시값과 동일해진다.

 

예를 하나 더 들어 접두어관계가 아닌 경우도 가정해보자.

353919와 3544중 문자열의 길이가 더 긴 것은 전자이므로

문자열의 길이를 맞추기 위해 353919에서 "19" 부분에 계산되었던 해시값을 빼어도 3544의 해시값과 다르다.

 

문자열의 길이를 맞추기 위해 뒷 부분에 계산된 해시값을 빼주는 함수는 아래 소스코드에서 hashmatch 함수이다.

(_hash함수는 문자열자체의 해시값을 구하여 반환하는 함수)

 

이런 식으로 수행하여 접두어가 동일한 경우가 하나라도 나온다면 solution 함수에서 false를 리턴하면 끝난다.

반대로, 접두어 관계를 하나도 발견하지 못했을 경우 마지막에 true를 리턴하면 된다. 

 

정확성, 효율성에서 모두 만점을 받은 접근법이었다.

 

이 문제에서는 메인문을 만들지 말고 solution 함수만 작성하라고 했기 때문에,

추가로 작성한 것은 solution함수, 정렬, 제곱에 필요한 헤더파일 밖에 없다.

 

#include <iostream>
#include <algorithm>
#include <math.h>
#include <string>
#include <vector>

using namespace std;
int _hash(string s){
	int hashcode=0;
	int power = 19;
	for (int i = 0; i < s.length(); i++) {
		hashcode += ((int)s[i])*pow(2, power - i);
	}
	return hashcode;
}
int hashmatch(string s,int hashcode,int start,int length){
	int power=start;
	int _hashcode=hashcode;
	int s_start=19-start;
	for(int i=s_start;i<s_start+length;i++){
		_hashcode-=((int)s[i])*pow(2,power);
		power--;
	}
	return _hashcode;
}
bool solution(vector<string> phone_book){
	vector<pair<string,int> >v;
    for(int i=0;i<phone_book.size();i++){
    	int hashcode = _hash(phone_book[i]);
    	v.push_back(make_pair(phone_book[i],hashcode));
	}
		
	sort(v.begin(),v.end());
	
	for(int i=1;i<v.size();i++){
		int l1=v[i-1].first.length();
		int l2=v[i].first.length();
		if(v[i].second==v[i-1].second) return false;}
		if(l2>=l1){
			int match_hash = hashmatch(v[i].first,v[i].second,19-l1,l2-l1);
			if(match_hash==v[i-1].second) return false;
		}
		else{
			int match_hash = hashmatch(v[i-1].first,v[i-1].second,19-l2,l1-l2);
			if(match_hash==v[i].second) return false;
		}
	}
	return true;
}