완주하지 못한 선수 해쉬로 풀기 자바스크립트

해쉬문제니까 해쉬로 풀었다.

해당 문제를 이중 for문을 이용해서 푸는 방법도 있지만,

그렇게하면 시간복잡도가 n^2으로 늘어나기도하고 일단 그건 해시 풀이가 아니어서..

어떤 주제로 문제가 주어지면 최대한 그 주제에 익숙해지기 위해서 해당 주제로 풀려고한다...

function solution(participant, completion) {
	const HashTable = {};
	let key;

// Add : 해쉬충돌까지 고려했다.
	for (key of participant) {
		if (!HashTable[key]) {
			HashTable[key] = 1;
		} else {
			HashTable[key] = HashTable[key] + 1;
		}
	}
    
// Search
	for (key of completion) {
		HashTable[key] = HashTable[key] - 1;
		console.log(HashTable);
	}

	for (key in HashTable) {
		if (HashTable[key]) {
			return key;
		}
	}
}

solution(
	["marina", "josipa", "nikola", "vinko", "filipa"],
	["josipa", "filipa", "marina", "nikola"]
);

처음 문제풀이를 할 때에는 단순히 빈 테이블에 주어진 배열의 값들을 넣었는데,

그렇게하다보니 해시충돌이 있는 테스트케이스에 걸렸다.

그래서 해시테이블에 추가할 때 중복되는 선수명을 고려해 다시 코드를 짰다.

• 위 풀이의 시간복잡도는 저장할 때 O(n), 탐색할 때 O(n), 평균적으로 O(n)만큼의 시간복잡도를 갖는다.