[프로그래머스/알고리즘] 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 

전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119 

박준영 : 97 674 223 

지영석 : 11 9552 4421 

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

해결방법

이 문제를 해결하는 방법은 모든 전화번호부를 일일이 비교하는 방법을 사용하면 매우 간단합니다. 

하지만 효율성 검사를 하기 때문에 좀더 적게 비교하고 빨리 답을 찾아내는 방법을 찾아야 합니다.

그래서 0~9까지의 해시 테이블을 배열로 만들고

각 번호의 첫번째 숫자를 기준으로 저장해서 해당 해시에 비교해서 맞는게 있는지 확인하는 방법을 이용했습니다.

해쉬테이블을 만들 때 예로 들면 1로 시작하는 경우가 여러 개일 경우를 저장하려면 2차원 배열을 이용해서 저장하면 됩니다.

그리고 해시에 저장하면서 먼저 저장하는 값과 비교해서 맞는게 있으면 false를 반환하고 없으면 계속 반복문을 실행하는 형식을 이용합니다.

소스코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;

bool solution(vector<string> phone_book) {
	bool answer =true;
	int k;
	vector<vector<string>> hash(10);

	for (int i = 0; i < phone_book.size(); i++) {
		k = phone_book[i][0] - '0';
		hash[k].push_back(phone_book[i]);
		for (int j = 0; j < hash[k].size() - 1; j++) {
			if (hash[k][j].compare(0,hash[k][hash[k].size() - 1].size(), hash[k][hash[k].size() - 1])==0)
				return false;			
			else if (hash[k][hash[k].size() - 1].compare(0, hash[k][j].size(),hash[k][j]) == 0)
				return false;			
		}
	}
	return answer;


}