[Hash, 난이도 중하] 프로그래머즈, 완주하지 못한 선수

참가자, 완주자들의 명단이 모두 주어졌을 때, 완주하지 못한 선수를 출력하는 문제이다.

완주자 = 참가자 - 1 이다. 즉 완주하지 못한 선수는 항상 1명이라는 것이다.

 

왼쪽 열부터 참가자, 완주자, 리턴값(완주하지 못한 선수) 이다.

[leo, kiki, eden]	[eden, kiki]	leo
[marina, josipa, nikola, vinko, filipa]	[josipa, filipa, marina, nikola]	vinko
[mislav, stanko, mislav, ana]	[stanko, ana, mislav]	mislav

이 문제의 취지에 맞게, 해시값을 이용하여 문자열 매칭을 하였다.

해시를 이용하여 풀었더니 정확성 만점, 효율성 만점을 받았다.

그런데 이 문제를 푼 후, 다른사람들이 짠 코드도 봤는데 해시를 이용하지 않고 문자열들을 정렬해도 통과처리 된 모양이었다.

아마 단순 정렬로 풀면 문제의 취지에도 맞지 않고, 데이터 범위(이름 길이, 참가자 수)가 좀만 더 넓었어도 효율성에서 좋은 점수를 받지 못했을 것이다. 

 

해쉬 부여 방법은 문자열의 각 문자의 아스키코드 값에 [2^문자의 인덱스]를 곱하여 전부 더하는 방법을 썼다.

첨부한 소스 코드 line 16 -> hash += ((int)participant[i][j])*pow(2, power - j);

 

이렇게 참가자, 완주자의 해쉬 코드값을 모두 계산하여 각각의 벡터에 넣고 이들을 정렬하였다.

문자열끼리의 정렬보다는 정수끼리의 정렬이 시간복잡도가 더 낮을 것이다.

정렬 후, 순차적으로 각 벡터의 동일한 인덱스를 탐색하다가 해시값이 다른 결과가 나왔을 때,  참가자쪽 해시값을 가지는 문자열(참가자 명)이 이 문제의 원하는 출력값이 되는 것이다.

 

해시값을 다시 문자열로 바꾸는 과정은 까다로우므로, 참가자쪽 벡터에 해쉬값을 push_back 했을때 인덱스 값까지 같이 넣어줬다. 두 값을 동시에 넣을 때 pair을 이용한 것이 그 이유다.

첨부한 소스 코드 line 18 -> a.push_back(make_pair(hash,i));

 

[만점 코드]

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

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

 

#include <algorithm>
#include <math.h>
#include <string>
#include <vector>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
	bool found = false;
	vector<pair<int,int> > a;
	vector<int> b;
	for (int i = 0; i < participant.size(); i++) {
		int hash=0;
		int power = participant[i].length() - 1;
		for (int j = 0; j < participant[i].length(); j++) {
			hash += ((int)participant[i][j])*pow(2, power - j);
		}
		a.push_back(make_pair(hash,i));
	}
	for (int i = 0; i < completion.size(); i++) {
		int hash = 0;
		int power = completion[i].length() - 1;
		for (int j = 0; j < completion[i].length(); j++) {
			hash += ((int)completion[i][j])*pow(2, power - j);
		}
		b.push_back(hash);
	}
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	for (int i = 0; i < b.size(); i++) {
		if (a[i].first != b[i]) {
			answer = participant[a[i].second];
			found = true;
			break;
		}
	}
	if (!found) answer = participant[a[a.size() - 1].second];
	return answer;
}