-
완주하지 못한 선수알고리즘/프로그래머스(PRPGRAMMERS) 2021. 10. 7. 10:42반응형
https://programmers.co.kr/learn/courses/30/lessons/42576
문제
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
- completion의 길이는 participant의 길이보다 1 작습니다.
- 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
- 참가자 중에는 동명이인이 있을 수 있습니다.
입력
Participant Completion ["marina", "josipa", "nikola", "vinko", "filipa"] ["josipa", "filipa", "marina", "nikola"] 출력
"Vinko"
접근법
- 문제가 Hash 카테고리인 만큼 Participant 와 Completion 이 중복되지 않도록 해결해야 한다.
- 처음에는 find 함수로 간단히 풀려 했지만, 중복되어 있는 이름이 있어, Participant 에서 지우고, 다시 순회하는 형식의 불필요한 일이 발생되었다.
- 따라서 MAP 을 사용하여 Completion에서 이름을 Count 해주었고, Count 가 완료 되면, Participant에서 하나씩 빼주었다. 그리고 <0 이 되는 순간 완주하지 못한 사람이 발생하였으므로, return
#include <string> #include <vector> #include <iostream> #include <map> using namespace std; string solution(vector<string> participant, vector<string> completion) { string answer = ""; map<string, int> count; for (auto c: completion){ count[c]+=1; } for (auto p: participant){ count[p]-=1; if (count[p] < 0) return p; } return answer; }
반응형'알고리즘 > 프로그래머스(PRPGRAMMERS)' 카테고리의 다른 글
가장 먼 노드 (0) 2022.04.29 입국심사 (0) 2022.04.29 N으로 표현 (0) 2022.04.29 프로그래머스[HASH] 위장 (0) 2021.10.11 프로그래머스_주식가격(Lv2) (0) 2021.04.19