알고리즘 문제 분석

프로그래머스의 완주하지 못한 선수라는 문제를 풀면서 생각한 것들을 정리해봤다.

문제
https://school.programmers.co.kr/learn/courses/30/lessons/42576

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항
1. 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
2. completion의 길이는 participant의 길이보다 1 작습니다.
3. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
4. 참가자 중에는 동명이인이 있을 수 있습니다.

(1)
우선 이 문제의 약점인 completion은 무조건 participant보다 1개 적다는 것을 이용해서 해결했다.
처음으로 해결한 방식은 sort() 함수를 이용해 participant와 completion을 정렬하고 앞에서부터 차례대로 비교해서 다른 것이 나올 때까지 비교한 것이었다.
(javascript는 indexoutofbound 에러가 뜨는 대신 undefined가 반환되서 마지막 요소도 비교를 해도 됐다.)

function solution(participant, completion) {
    participant = participant.sort();
    completion = completion.sort();

    for (i in participant) {
    	if (participant[i] !== completion[i]) {
            return participant[i];
        }
    }
}

(2)
나는 이 방식이 다른 상황에 적용하기 어려운 방식이라는 생각이 들어서 좀 더 문제의 출제 의도에 대해 고민해봤다.
그리고 배열끼리 비교하는 방법이 없을까 생각을 하다가 completion 배열의 이름을 하나 하나 찾아서 participant의 동일한 이름을 하나 하나 제거하는 방식을 사용해봤다.

아래와 같은 코드는 문제를 해결하긴 했지만 시간 초과를 내서 프로그래머스의 효율성 테스트를 통과하지 못했다.

function solution(participant, completion) {

    for (let i = 0; i < completion.length; i++) {
        let completePartiIndex = participant.indexOf(completion[i])
        if (completePartiIndex == -1) {
            return completion[i];
        } else {
            participant.splice(completePartiIndex, 1);
        }
    }

    return participant[0];
}

(3)
두 배열간의 교집합이나 차집합을 이용하는 방식이 없는지 생각을 해봤고 아래와 같은 차집합의 기본 구조를 알게 되었다.
그런데 결국 SET과 같은 집합 자료구조는 중복이 있을 때는 문제를 제대로 해결하지 못하는 듯 하여 포기했다.
(arr1에서 arr1과 arr2의 교집합을 제거하는 arr1-arr2 차집합을 구하는 방식이다.)

let difference = arr1.filter(x => !arr2.includes(x)); 

(4)
마지막으로 해시를 이용하는 방법을 사용했다.
js 객체를 하나 만들고 (변수명을 hash라고 지음) completion 배열의 이름을 key에 중복되있는 숫자를 value에 저장한다.
그리고 participant 배열에 있는 이름이 있을 때마다 hash의 해당 이름의 값을 1씩 줄이고 0보다 작아지는 값이 있을 때 해당 이름이 통과하지 못한 한 사람이 되는 알고리즘이다.

function solution(participant, completion) {
    // 그냥 객체 생성한 거
    const hashMap = {};
    for (let hash of completion) {
        // 객체에 값이 없으면 1을 할당하고 있으면 1을 증가시킨 후 할당한다.
        hashMap[hash] = hashMap[hash] ? ++hashMap[hash] : 1;
    }

    for (let part of participant) {
        // 객체에 participant 이름이 없으면 해당 이름 반환함
        if (!hashMap[part]) return part;
        hashMap[part]--;
    }
}

알게 된 점

중복이 있는 자료구조끼리 비교할 때는 해시 구조(key-value 형식)를 사용하면 좋을 것 같다.

그리고 오늘의 일을 통해 어떤 문제를 깊게 파고들어가는 것의 재미를 알게 된 것 같다.