[Programmers] 완주하지 못한 선수

간만에 문제풀이를 위해 들어갔는데..

바보가 된 느낌이다

 

전에는 이렇게 안풀었겠지만 오랜만에 c++을 만지면서 STL사용이 너무 어색해져서 답을 알면서 구현을 못하는 말도 안되는 상황까지 온듯하다... 반성하자..

 

너무나도 간단한 주제,, 두 string 리스트를 비교해서 중복되지 않는 하나의 string을 뽑아내는 문제였다.

 

처음에 생각났던 풀이는 HashMap이라는 주제에 맞춰서 Map을 구성해서 비교한 풀이였고

나중에 생각났던 풀이는 좀더 짧고 간단한 풀이였는데 뒤에있는풀이가 좀더 재밌는 풀이인것 같다.

 

우선 HashMap이라는 주제에 고정시킨 풀이부터 설명해보자면

1. 입력된 string값들을 hashing해서 hashValue, string을 한쌍으로 해서 Map에 집어넣는것을 두 string 리스트에 대해 수행

2. 두번째 Map의 key 값들을 첫번째 Map에서 없애줌

3. 문제 상황에서 두 string list의 원소 개수 차는 1개라고 했기 때문에 첫번째 Map의 하나남은 원소가 중복되지 않는 하나의 string이된다.

-> 여기서 하나 주의 할 점은 리스트에 중복된 string이 들어갈수도 있다는 점이었는데, 이 경우 hashValue가 중복이되어서 Map의 값이 덦어씌워질수도 있다는 생각이 들어서 만약에 hashValue가 Map에 Key로 들어있다면 hashValue값을 두배씩 올려서 중복되지 않는 key 값을 구성하도록 했다.

 

이 풀이에 대한 코드는 아래와 같습니다.

#include <string>
#include <vector>
#include <map>

using namespace std;

const long long base = 31;
const long long MOD = 1e9 + 9;

long long getHashValue(string p) {
	long long val = 0;
	for (int idx = 0; idx < p.size(); ++idx) {
		val *= base;
		val %= MOD;
		val += p[idx];
		val %= MOD;
	}
	return val;
}

string solution(vector<string> participant, vector<string> completion) {
	map<long long, string> pMap, cMap;
	long long hashValue;
	for (int idx = 0; idx < participant.size(); ++idx) {
		hashValue = getHashValue(participant[idx]);
		while(pMap.count(hashValue) > 0) {
			hashValue *= 2;
			hashValue %= MOD;
 		}
		pMap.insert(make_pair(hashValue, participant[idx]));
	}
	for (int idx = 0; idx < completion.size(); ++idx) {
		hashValue = getHashValue(completion[idx]);
		while(cMap.count(hashValue) > 0) {
			hashValue *= 2;
			hashValue %= MOD;
		}
		cMap.insert(make_pair(hashValue, completion[idx]));
	}

	map<long long, string>::iterator iter;
	for (iter = cMap.begin(); iter != cMap.end(); ++iter) {
		pMap.erase(iter -> first);
	}

	return pMap.begin()->second;
}

 

나중에 생각난 좀더 단순한 풀이는 

1. 입력으로 들어오는 두 string 리스트를 정렬한다. 

2. 짧은 리스트의 길이 기준으로 두 리스트를 비교, 만약에 중간에 다른 부분이 존재한다면 그 값이 중복되지 않은 string 값이라고 반환.

3. 순회가 끝났는데 다른게 없으면 긴 리스트의 마지막 값이 중복되지 않은 string이라고 반환.

-> 문제 상황에서 string의 최대 길이가 20까지라고 명시를 했기때문에 string 리스트를 대놓고 정렬할수 있었던것 같다.

string이 지나치게 길어졌다면 정렬에서 시간이 너무 많이 걸릴수도 있으러것 같다.

 

이 풀이에 대한 코드는 아래와 같습니다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
	sort(participant.begin(), participant.end());
	sort(completion.begin(), completion.end());

	int size = completion.size();
	for (int idx = 0; idx < size; ++idx) {
		if (participant[idx] != completion[idx]) {
			return participant[idx];
		}
	}

	return participant[participant.size() - 1];
}

확실히 두번째 풀이가 나중에 생각이 정리되고 나서 적은거라 그런지 더 깔끔한듯 하다.