[프로그래머스/C++] ㅡ LV1 - 완주하지 못한 선수

문제

programmers.co.kr/learn/courses/30/lessons/42576

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

풀이

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    map<string, int> h1;
    for (string name : participant) {	// 초기화
        ++h1[name];
    }
    for (string name : completion) {	// 수정
        --h1[name];
    }
    for (auto pair : h1) {	// 확인
        if (pair.second > 0)
           return pair.first;
    }
}

개념

C++ STL의 map을 사용한다.

이는 균형 이진 트리 구조로, key와 value로 이뤄져 있는 pair 형태이다.

O(logn)의 시간복잡도를 가진다.

h1[key] = value 로 원소를 저장 및 변경할 수 있다.

---

풀이

배열 participant를 사용해서 h1에 key 값(이름)과 value를 초기화 한다.

이 값은 1, 2, 3 순으로 + 되는 양의 정수이다.

 

다음으로 배열 completion을 사용해 h1에 기존 key값(이름)에 해당하는 value를 변경한다.

이 값은 -1, -2, -3 순으로 - 되는 음의 정수이다.

 

오직 완주하지 못한 선수(key)만 양의 정수(value)를 갖게된다. 

초기화 / 수정 / 확인

.

 

---

+a

 

 

다른풀이(실패..)

#include <string>
#include <vector>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    for (int i=0; i<participant.size(); i++) {
        for (int j=0; j<completion.size(); j++) {
            if (participant[i] == completion[j]) {
                participant.erase(participant.begin()+i);
                completion.erase(completion.begin()+j);
                i--;
                j--;
                break;
            }
        }
    }
    string answer = participant[0];
    return answer;
}

이 문제에서 상정한 바에 따르면 선수는 최대 100000명이다.

이를 이중 for문을 통해 탐색하는 경우 O(n^2)의 시간복잡도이고, 시간초과가 발생한다.

 

unordered_map을 사용해 hash Table을 사용할 수도 있다. 이 경우 정렬의 계산이 없으므로 O(1)의 시간복잡도를 가진다.

다른 방법으로, 각 배열에 sort를 사용하고, 이중 for문 대신 한번의 반복문만 사용할 수도 있다.

이 경우 sort에 해당되는 O(nlogn)의 시간복잡도를 가진다.