[PS] 완주하지 못한 선수 (c++, js)

프로그래머스

문제

참가자 명단과 완주자 명단을 비교하여 완주하지 못한 선수 찾기

 

풀이

이 문제는 프로그래머스의 알고리즘 고득점 Kit의 해시에 속하는 문제다.

해시 문제는 정렬로 풀리는 경우가 많은데, 정렬로 푸는 방법이 더 간단해서 찾아보면 정렬 풀이법이 많이 나온다.

나는 해시를 이용한 정석 풀이법과 정렬을 이용한 풀이법까지 총 두 가지 방법으로 풀어보겠다!

 

정렬

(1) 정렬하기

참가자 명단과 완주자 명단을 보면, 완주자 명단에 속한 사람은 모두 참가자 명단에도 속한다는 것을 알 수 있다.

그렇다는 말은 각 배열을 같은 기준으로 정렬하면  동일한 배열이 나온다는 것이다.

한 가지 다른 점은 1명의 미완주자가 있으므로, 그 1명만 제외하면 모두 동일하다.

이때 배열의 크기도 다르므로 주의해야 한다!

*미완주자 배열 크기 = 완주자 배열의 크기 - 1

(2) 미완주자 찾기

참가자 [A, B, C] 완주자 [A, C]

정렬하여 위와 같은 배열이 나왔다고 하자.

인덱스를 하나씩 증가하며 값을 비교할 때, 각 배열에서 다른 값이 나왔다는 것은 참가자 배열에 있는 선수가 완주하지 못했다는 것을 뜻한다.

 

코드 1

#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());
    
    for (int i = 0; i < participant.size(); i++){
        if (i == participant.size() - 1){
            return participant[i];
        }
        else if (participant[i] != completion[i]){
            return participant[i];
        }
    }
}

function solution(participant, completion) {
    participant.sort();
    completion.sort();
    
    for (let i = 0; i < participant.length; i++) {
        if (participant[i] !== completion[i]) {
            return participant[i];
        }
    }
}

 

해시

(1) 해시 맵 사용하기

key와 value를 저장할 수 있는 map을 사용한다.

key에는 이름을 저장하고, 동명이인이 있을 수 있으므로 value에는 인원수를 저장한다.

(2) 미완주자 찾기

참가자 명단을 바탕으로 맵을 만들고, 완주자 명단에 있는 사람들을 확인하며 value의 값을 1씩 감소시킨다.

반복문을 마친 뒤, 최종적으로 value가 0이 아닌 key가 미완주자인 것이다.

 

코드 2

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_map<string, int> participantMap;
    
    for (string p : participant) {
        participantMap[p]++;
    }
    
    for (string c : completion) {
        participantMap[c]--;
    }
    
    for (auto pair : participantMap) {
        if (pair.second > 0) return pair.first;
    }
}

function solution(participant, completion) {
    const participantMap = new Map();
    
    for (const p of participant) {
        participantMap.set(p, (participantMap.get(p) || 0) + 1);
    }
    
    for (const c of completion) {
        participantMap.set(c, participantMap.get(c) - 1);
    }
    
    for (const [key, value] of participantMap) {
        if (value > 0) {
            return key;
        }
    }
}

 

회고

알고리즘 스터디를 하면서 다시 한번 문제를 풀게 됐다!

처음에는 정렬 방식으로만 풀고 C++로 했었는데, 이번에는 해시까지 포함해서 js로도 풀어보니 더 이해도가 깊어진 느낌이다.