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

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

프로그래머스

#해시 #lv.1

 

회고

✔ 시간 초과

테스트 케이스는 통과하였으나 제출을 하니 2문제를 뺀 문제들이 전부 실패가 뜨고 효율성 문제에서 죄다 실패해서 문제 접근 방법이 잘못되었음을 깨달았다. (태그에 해시 있을때부터 짐작은 했지만 ㅜㅜ)

 

아무튼 처음엔 그냥 브루트포스로 무작정 문자열을 비교해줬는데 이때문에 효율성이 엄청 떨어졌던 것같다.그래서 참가 명단이랑 완주 명단을 정렬해줬고, 그 결과 맞출 수 있었다.

 

아, 조금 고민했던 부분은 정렬을 해줬을 때, 만약 완주 못한 사람이 마지막 사람일 경우를 대비해서 check 배열을 통해 완주 여부를 체크해줬다.

 

코드

#include <string>
#include <vector>
#include <algorithm>
#define MAX 100000
using namespace std;

int check[MAX] = { 0, }; //완주한 선수 저장

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    vector<string> tmp;
    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for (int i = 0; i < completion.size(); i++) {
        if (completion[i].compare(participant[i])) {
            answer = participant[i];
            break;
        }
        check[i] = 1;
    }
    if (answer == "") {
        for (int i = 0; i < participant.size(); i++) {
            if (check[i] == 0) {
                answer = participant[i];
                break;
            }
        }
    }
    return answer;
}