[programmers] 프로그래머스 완주하지 못한 선수(C++)

(주)그렙

[programmers] 프로그래머스 완주하지 못한 선수

(C++)

(글쓴날 : 2020.06.06)

 

---

* programmers, 프로그래머스 문제 C++ 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 완주하지 못한 선수

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42576#

코딩테스트 연습 - 완주하지 못한 선수

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

마라톤 경기에 참여한 선수의 목록과, 완주한 선수의 목록이 주어질 때, 완주하지 못한 선수의 이름을 알아내는 문제입니다.

 

저의 경우, 이진 탐색 트리를 적용했으며, C++를 사용했습니다.

이진 탐색 트리를 두 개 만들어 각 목록의 이름을 저장하였고, 각 트리에서 이름의 개수가 다른 것을 구해 문제를 해결했습니다.

단, 마라톤 선수의 이름이 중복될 수 있기에 중복된 key 값을 가질 수 있는 multiset으로 구현했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <string>
#include <vector>
#include <set>
 
using namespace std;
 
string solution(vector<string> participant, vector<string> completion)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    string answer = "";
 
    multiset<string> s1;
    multiset<string> s2;
 
    for (int i = 0; i < participant.size(); i++)
        s1.insert(participant[i]);
 
    for (int i = 0; i < completion.size(); i++)
        s2.insert(completion[i]);
 
    for (int i = 0; i < participant.size(); i++)
    {
        if (s1.count(participant[i]) != s2.count(participant[i]))
            answer = participant[i];
    }
 
    return answer;
}

---