[프로그래머스] 완주하지 못한 선수 (c++)

출처 : 코딩테스트 연습 - 완주하지 못한 선수 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 완주하지 못한 선수

 

 

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";
    sort(completion.begin(), completion.end());
    sort(participant.begin(), participant.end());
    int i = 0;
    while(completion[i] == participant[i]) {
        i++;
    }
    answer = participant[i];
    return answer; 
}

 

처음에 completion 수 만큼 for 문을 돌며 participant 에서 제거해주는 방식으로 풀이를 했는데 이런 식으로 풀게되면 시간 복잡도가 O(n^2) 이 나와 시간초과로 풀지 못한다.

그래서 미리 각 벡터를 sort한후 인덱스(i) 0부터 completion, participant 벡터의 인덱스 값이 같으면 인덱스 값을 1씩 더해가다 다를시 while 문을 탈출하며 answer 에 participant 값을 넣어주면 답이 된다