프로그래머스 문제 풀이 완주하지 못한 선수

 이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다.

문제 URL : 완주하지 못한 선수

Contents

1. 문제 지문 파악하기
2. 강사님의 알고리즘 풀이
3. 구르미의 알고리즘 풀이

문제 지문 파악하기

문제에서 중요한 키 포인트는 2가지입니다.

 

1. 동명이인이 있을 수 있다.
2. 완주하지 못한 사람을 딱 1명이다.

가장 쉽게는 "completion"을 순회하면서, "participant"에서 같은 이름을 삭제하면 됩니다. 동명이인일 경우는 먼저 나온 이름을 삭제하고 그러다보면, 이름이 1개가 남을 것입니다. 코드는 이렇게 될겁니다.

 

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";

    for (const auto & x : completion){
        int idx = 0;

        for (const auto p : participant) {
            if (p == x) {
                break;
            }

            idx += 1;
        }

        participant.erase(participant.begin() + idx);
    }

    answer = participant[0];
    return answer;
}

 

이 경우, 시간 복잡도는 O(N ^ 2)입니다. 코드를 제출해보면, 정확성 테스트는 통과하지만, 효율성 테스트에서 "시간 초과"라는 결과를 얻게 됩니다. 효율성을 올릴 필요가 있죠. 효율성을 올리는 방법은 크게 2가지가 있습니다.

 

• 동적계획법, 탐욕법 등의 알고리즘 패러다임을 적용한다.
• 해시, 트리 등 적절한 자료구조를 적용한다.

여기서 우리는 후자를 선택할겁니다. 이 문제를 풀기 위한 적절한 자료구조인 해시를 적용하여 알고리즘 성능을 올려보겠습니다. 해시란 "키-값" 쌍으로 저장하는 형태의 자료구조입니다. 해싱 함수를 통해 키를 통해서 값을 가져오는데 O(1)의 시간이 걸리지요. 이제 어떻게 올릴것이냐.

 

이 문제에서 중요한 점은 앞서 언급했듯이 "동명 이인이 있을 수 있다"입니다. 이것과 해시를 이용하면 문제를 해결하는 쉽습니다. 등록한 참가자를 모두 해시에 저장합니다. 어떻게 저장하냐? { 이름 : 동명이인의 수 }로 저장합니다.

 

첫 번째 입력을 통해 살펴볼까요?

 

입력 :
      participant: ["leo", "kiki", "eden"]
      completion: ["eden", "kiki"]

 

이 경우 먼저 participant를 순회하여 이름을 키로 해시를 만듭니다.

 

participant를 순회하여 저장된 해시 값 :
    { "leo": 1, "kiki": 1, "eden": 1 }

 

그 후, completion을 순회하여 이름을 키로 쌍으로 저장된 "동명 이인의 수"의 수를 1 줄입니다.

 

completion을 순회하여 동명이인의 수를 줄인 해시 값 :
    { "leo": 1, "kiki": 0, "eden": 0 }

 

이렇게 해서, 동명이인의 수가 0이 아닌 값을 가진 키 "leo"를 반환하면 됩니다.

 

이어서 동명이인이 있는 세 번째 입력도 살펴보겠습니다.

 

입력 :
    participant: ["mislav", "stanko", "mislav", "ana"]
    completion: ["stanko", "ana", "mislav"]

 

먼저 participant를 순회하여 이름을 키로 해시를 만듭니다.

 

participant를 순회하여 저장된 해시 값 :
    { "mislav": 2, "stanko": 1, "ana": 1 }

 

그 후, completion을 순회하여 이름을 키로 쌍으로 저장된 "동명 이인의 수"의 수를 1 줄입니다.

 

completion을 순회하여 동명이인의 수를 줄인 해시 값 :
    { "mislav": 1, "stanko": 0, "ana": 0 }

 

이렇게 해서, 동명이인의 수가 0이 아닌 값을 가진 키 "mislav"를 반환하면 됩니다. 어떻게 알고리즘이 동작하는지 아시겠지요? 다음 절에서 실제로 문제를 풀어봅시다.

강사님의 알고리즘 풀이

'문제 지문 파악하기'에서 세운 알고리즘을 간단하게 나타내면 다음과 같습니다.

 

1. { 이름: 같은 이름의 인원 수 } 쌍의 해시를 만듭니다.
2. 등록한 사람 이름 목록 participant에 존재하는 사람 이름을 해시에 저장합니다.
3. 완주한 사람 이름 목록 completion에 존재하는 사람 이름에 대해서 해시에 저장된 해당 이름의 인원 수를 1 줄입니다.
4. 사전에 등록된 { 이름: 인원 수 } 쌍 중 인원 수가 0보다 큰 사람 이름을 반환합니다.

코드로 표현하면 다음과 같습니다.

 

def solution(participant, completion):
    d = {}

    for x in participant:
        d[x] = d.get(x, 0) + 1
    
    for x in completion:
        d[x] -= 1

    answer = [k for (k, v) in d.items() if v > 0][0]
    return answer

 

이 문제의 최악의 시간 복잡도는 O(N)입니다. 해시를 통해 데이터를 가져오는 건 O(1)이기 때문에 인원 수 N에 대해서 비례하게 시간이 걸리기 때문입니다.

 

또한 이 문제는 정렬을 통해서도 해결할 수 있습니다. 그러나 시간 복잡도는 O(Nlog(N))이기 때문에, 해시를 이용한 풀이보다 효율적이지는 못합니다. 정렬을 이용한 문제 풀이 코드는 다음과 같습니다.

 

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]

    return participant[-1]

 

구르미의 알고리즘 풀이

제가 푼 코드는 다음과 같습니다. 뭔가 강사님 코드에 비해서 파이써닉하지 않은게 보이네요..

 

def solution(participant, completion):
    # 1. { '사람이름': 인원 수 } 형태의 해시를 만듭니다.
    d = dict()
    
    # 2. 모든 참가자를 이름: 인원 수 쌍으로 해시에 저장합니다.
    for p in participant:
        if p not in d:
            d[p] = 0
        
        d[p] += 1
    
    # 3. 완주한 선수의 이름을 보고 해시에서 해당 이름 쌍으로 저장된 인원 수를 1 줄입니다.
    #    만약, 0이라면, 해시에서 이름을 제거합니다.
    for p in completion:
        d[p] -= 1
        
        if d[p] == 0:
            del d[p]
    
    answer = list(d.keys())[0]
    return answer

# 실행을 위한 main 함수입니다.
if __name__ == '__main__':
    participant = ["marina", "josipa", "nikola", "vinko", "filipa"]
    completion = ["josipa", "filipa", "marina", "nikola"]
    result = solution(participant, completion)
    print(result)

 

cpp는 다음과 같습니다. 번갈아서 보면 좋을 것 같군요.

 

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

// main 출력을 위한 헤더
#include <iostream>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    map<string, int> d;
    
    for (const auto& x : participant) {
        d[x] = (d.find(x) == d.end() ? 0 : d[x]) + 1;
    }
    
    for (const auto& x : completion) {
        d[x] -= 1;
    }
    
    for (const auto& elem : d) {
        if (elem.second > 0) {
            answer = elem.first;
            break;
        }
    }
    
    return answer;
}

int main() {
    vector<string> participant = { "marina", "josipa", "nikola", "vinko", "filipa" };
    vector<string> completion = { "josipa", "filipa", "marina", "nikola" };
    const auto result = solution(participant, completion);
    cout << result << endl;
    return 0;
}