[프로그래머스] 완주하지 못한 선수△
in CodingTest
이 문제를 읽고 처음 든 생각은 엄청 간단하네 하고 find알고리즘을 이요하여 플려고 했다. 물론 테스트 케이스도 다 통과하고 문제도 통과하는데 효윻성 문제에서 0점이 나왔다. 그래서 어떤식으로 해야 효율성이 좋아질까 고민하다 생각한게 map컨테이너를 이용하여 동일인물이 있을 때 까지 해결하는 방법을 생각한 것이다.
우선, 코드를 보자.
#include <string>
#include <vector>
#include<map>
#include<algorithm>
using namespace std;
string solution(vector<string> participant, vector<string> completion) {
string answer = "";
map<string,int> m;
for (int i = 0; i < participant.size(); i++) {
pair<map<string, int>::iterator, bool> p = m.insert(make_pair(participant[i], 0));
if (p.second == false) {
m[participant[i]] += 1;
}
}
for (int i = 0; i < completion.size(); i++) {
m[completion[i]] -= 1;
}
for (int i = 0; i < participant.size(); i++) {
if (m[participant[i]] >=0) {
return participant[i];
}
}
}
풀이
(1) map<string,int> 컨테이너를 사용해 참가자의 이름과 참가자 명수를 저장한다.(여기서 이미 동일 이름이 있다면 참가자 명수를 증가 시킨다.)
(2) 완주자 명단에서 그 이름에 해당하는 참가자 명수를 1씩 감소한다.
(3) map컨테이너를 돌면서 int 값이 0이상인 사람이 완주하지 못한게 되므로 그 사람의 이름을 return 한다.
위와 같이 풀었더니 효율성 문제까지 해결 되었다.
하지만 이 문제 풀이가 △인 이유는 다른 사람의 풀이를 봐보니 파라미터로 넘어논 두 vector를 정렬한 다음 서로 비교해서 처음으로 값이 달라진 부분이 완주 하지 못한 사람이란 방법으로 풀었는데 이처럼 깔끔하게 풀 수 있는 방법이 있기 때문에 △이다. 저렇게 창의적으로 문제를 푸는 습관을 들이도록 하자.
