[C++] 프로그래머스 hash 2 - 전화번호 목록

[Level 2]

 

처음 내 풀이

: 정확성 83.3(만점) 효율성 8.3 = 91.7 로 실패

 

bool solution(vector<string> phone_book) {
	sort(phone_book.begin(), phone_book.end());

	for (int i = 0; i < phone_book.size(); i++) {
		for (int j = i + 1; j < phone_book.size(); j++) {
			int split_size = phone_book[i].size();
			cout << phone_book[j].substr(0, split_size) << endl;
			if (phone_book[i] == phone_book[j].substr(0, split_size))
				return false;
		}
	}

	return true;
}

 

전화번호를 sort 한 뒤 길이가 짧은 원소를 기준으로 해 뒤의 것들에 접두사가 되는지 확인.

뒤의 것들을 모두 확인해야 하기 때문인지 효율성 케이스 두개가 시간 초과 되었다.

 

다른 사람의 풀이

 

bool solution(vector<string> phone_book) {
	sort(phone_book.begin(), phone_book.end());

	for (int i = 0; i < phone_book.size()-1; i++) {
		if (phone_book[i] == phone_book[i + 1].substr(0, phone_book[i].size()))
			return false;
	}
	return true;
}

 

어차피 접두사가 되는 것 하나라도 있으면 끝이므로 뒤의 것들을 모두 검사해야할 필요 없이, 바로 뒤의 것만 검사해도 된다. 위 풀이는 효율성 검사도 통과한다.

 

 

 

다른 사람의 풀이 - hash 이용

bool solution(vector<string> phone_book) {
	unordered_map<string, int> hash_map;

	for (int i = 0; i < phone_book.size(); i++) {
		hash_map[phone_book[i]]++;
	}
	for (int i = 0; i < phone_book.size(); i++) {
		string phone_num = "";
		for (int j = 0; j < phone_book[i].size(); j++) {
			phone_num += phone_book[i][j];
			if (hash_map[phone_num] && phone_num != phone_book[i])
				return false;
		}
	}
	return true;
}

 

번호 문자열을 해시맵에 등록한 후,

각 요소의 첫번째 자리부터 빈 문자열에 갖고와서 해시맵에 그 문자열이 등록돼있다면(phone_book 배열에 있다면) 원래 있던 문자열보다 더 길면(자기자신과 비교하는게 아니면) false를 반환한다.