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

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42576

 

문제 설명

1. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
2. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어졌을 때
3.완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

 

문제 입출력 예)

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

 

문제 풀이 1

참여자 - 완주자를 실행 할 경우, 단 한명의 참여자만이 나올 것이라 생각하였다.

그래서 while문을 통해 paricipant의 크기가 1이 아닐 경우 계속 실행하도록 하였다.

그 이후 완주한 사람과 참여한 사람의 값을 비교하여 참여한 사람의 값에 완주한 사람이 있다면 erase 함수를 사용해 참여자에서 지워주었다.

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    
    string answer = "";
    while(participant.size()!=1){
        for(int i=0; i<completion.size(); i++){
            auto p =find(participant.begin(), participant.end(), completion[i]);
            participant.erase(p);    
        }
        
    }
    return participant[0];
}

 

이와 같은 프로그램은 N*N번 O(N^2)번 실행하게 되기 때문에 정확성 테스트에서는 만족하였지만,

효율성 테스트에선 0점,,

 

 

문제 풀이 2

해시를 사용해서 문제풀이를 하도록 하였다.

map<String, int> race;로 명단과 값을 받아오고

우선 완주자의 명단에 각각 +1을 시켰다.

이후 참가자의 명단에 각각 -1을 실행시켜

참가자 중 음수가 나온 값을 출력하였다.

#include <string>
#include <vector>
#include <map>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    
    map<string, int> race;
    
    for(auto c : completion){
        race[c] += 1;
    }
    
    for(auto p : participant){
        race[p] -= 1;
        if(race[p] < 0)
            return p;  
    }
}

리뷰

• map<string, int> race;
• Hash를 잘 사용하는 방법에 대해 공부를 많이 해봐야겠다.
• 바로바로 문제푸는 방법이 생각나지 않아, 문제를 정말 많이 풀어봐야 할 것 같다는 생각이 들었다.