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

문제출처 : programmers.co.kr/learn/courses/30/parts/12077

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    vector<string>::iterator position1, position2;

    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for(int i = 0; i < participant.size(); i++) {
        if(participant[i] != completion[i]) {
            return participant[i];
        }
    }
}

참가자 명단 participant와 완주자 명단 completion을 비교하여 통과하지 못한 한명을 찾아내는 방식.

 

문제를 제대로 안읽고 처음에는 무식하게 반복문을 돌렸지만, 이후 최대 명단수가 10만이란것을 보고 코드를 싹다 뒤집어 엎었다.

 

최소한의 반복으로 결과에 다다르기 위하여 어떻게 풀까 생각을하다가, 문자열을 아예 정렬을 해버렸다.

 

정렬후에 하나씩 비교하며 두 위치의 이름이 다르면, 참가자 명단쪽의 이름을 가져온다. 그럼 그것이 통과하지 못한 한명이기 때문.

 

능지를 최대한 살려 풀어 보았고, 많은 사람들이 그렇게 풀었지만, 아래쪽에 있던 정답에 눈이 더 가고 말았다.

 

해시에 관련된 문제이기에 HashMap을 사용해야 했고, 그 문제를 보고 똑같이 작성해보며 새로운 지식을 챙기기로 하였다.

 

#include <string>
#include <vector>
#include <unordered_set>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    unordered_multiset<string> names;
    for(int i = 0; i < participant.size(); i++){
        names.insert(participant[i]);
    }
    for(int i = 0; i < completion.size(); i++){
        unordered_multiset<string>::iterator itr = names.find(completion[i]);
        names.erase(itr);
    }
    return *names.begin();
}

unordered_set 이라는 처음듣는 무언가를 사용했다.

 

unordered_multiset을 이용해 문자열을 받아올 수 있도록 선언해 주고, 참가자명단을 싹다 집어넣어준다.

 

그리고 완주자 명단을 싹다 돌리며, 순서대로 돌리며 완주자명단에 들어있는 이름을 참가자 명단에서 찾아내 삭제.

 

그 후에 결과를 리턴하는 방식이었다.

 

진즉에 알았다면 좋았을 지식이었다.

 

그리고 처음보는 것이 하나 있었는데, 마지막의 return *names.begin(); 에서의 * 별모양 이었다.

 

포인터참조 라는것으로 현실의 메모장 처럼 사용하는 느낌인듯 하다.