[프로그래머스] 완주하지 못한 선수 (Lv.1)

---

문제 링크

---

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

문제 설명

---

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참여자의 이름은 1개 이상 20개 이하의 소문자 알파벳으로 이루어져 있습니다.
• 참여자 중에는 동명이인이 있을 수 있습니다.

내 풀이

---

completion과 participant를 각각 해시맵으로 빈도를 센다. 두 맵을 모두 완성한 뒤 participant를 순회하며 p_counter[s] != c_counter[s]인 이름을 answer로 갱신한다. 완주하지 못한 선수는 participant에 completion보다 한 번 더 등장하므로 두 빈도가 반드시 다르고, 나머지 선수들은 빈도가 같아 조건에 걸리지 않는다.

#include <string>
#include <vector>
#include <unordered_map>

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    unordered_map<string, int> p_counter;
    unordered_map<string, int> c_counter;
    
    for(auto& s : completion)
    {
        c_counter[s]++;
    }
        
    
    for(auto& s : participant)
    {
        p_counter[s]++;
    }
    
    for(auto& s : participant)
    {        
        if(p_counter[s] != c_counter[s])
            answer = s;
    }
    
    return answer;
}

시간복잡도 분석

---

• completion 순회 (c_counter 구성): O(n)
• participant 순회 (p_counter 구성): O(n)
• participant 순회 (비교): O(n)
• 전체: O(n)

n ≤ 100,000이므로 충분히 통과 가능하다.

오답노트

---

처음에 p_counter를 구성하면서 동시에 비교했다. p_counter가 완성되기 전이면 아직 participant를 다 읽지 않은 상태이므로 완주한 선수도 p_counter[s] < c_counter[s]가 되어 != 조건이 true가 된다. 이 경우 완주한 선수가 answer에 잘못 저장되고, 이후에 덮어써지지 않으면 오답이 된다.

p_counter를 먼저 완성한 뒤 비교해야 한다.

후기

---

생각해보니까 굳이 카운터를 두개 두지 않았어도 됐던 것 같다.

unordered_map<string, int> counter;

for(auto& s : participant) counter[s]++;
for(auto& s : completion)  counter[s]--;

for(auto& [name, cnt] : counter)
    if(cnt > 0) return name;

return "";

이렇게 간단하게 풀 수 있을 것 같다.
아직 공부한 내용을 다 써먹지 못하는 것 같다. 조금 더 철저한 복습으로 잘 다져야겠다.

• algorithm
• codingtest
• hash