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

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

 

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

 

해당 문제의 알고리즘 분류는 해쉬 문제였다.

하지만 알고리즘 분류에 초점을 맞추지 않고 내 스스로 어떠한 알고리즘과 자료구조를 사용할지 생각해봤다.

 

곰곰히 생각해본 결과 정렬을 사용해서 문제를 풀어도 된다는 생각을 떠올리게 됐다.

 

문제 접근 과정:

 

1.정렬을 떠 올린 이유:

 

해당 문제의 핵심 키는 "한 명의 선수만 완주하지 못했다."이다.

이는 한 요소를 제외한 모든 것은 동일하다고 해석이 가능하다.



두 배열을 비교하면서 participant 배열에는 존재하나 completion에는 존재하지 않는 요소를 찾아내면 된다.

이때 비교를 어떠한 방식으로 할 것이냐가 문제의 효율을 판가름한다.



가장 쉬운 방법은 participant 배열의 모든 요소 각각을 completion 배열의 전체 요소와 비교해가면서 찾아가는

brute force 방식이다.

하지만 이는 O(2^n)의 시간 복잡도를 갖는다.

 

때문에 이보다 효율적인 방법인 정렬을 방법을 이용한다면 O(nlogn)(=정렬 비용)의 시간 복잡도로 문제를 해결할 수 있다.

1개의 요소 이외에는 나머지는 같다는 것을 포인트로 잡았다.

이는 순서대로 각 배열의 요소들을 접근하다 보면 일치하지 않는 요소가 생긴다.

이는 participant 배열에는 존재하나 completion 배열에는 존재하지 않는 요소이다.

 

2.예외 처리

participant 배열과 completion 배열의 크기는 같지 않음으로

정렬 시 participant 배열의 마지막 요소가 completion 배열의 마지막 요소와 같지 안은 경우가 있다.

이러한 예외의 경우 for 문을 돌려 index를 통해 비교하다 보면 예외 처리를 위한 코드가 추가되어

가독성을 떨어트릴 것이라 생각하였다.

그래서 while 문의 조건으로 completion 배열이 empty 일 때까지 돌리면서

배열의 마지막 요소를 비교한 후 pop을 해주었다.

마지막 요소들이 서로 다르다면 break를 통해 while 문을 탈출하였다.

 

 

 

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    //정렬
    sort(participant.begin(),participant.end());
    sort(completion.begin(),completion.end());
    
    
    while(!completion.empty()){ 
        
        if(completion.back().compare(participant.back())){//일치 x
            break;
        }
        
        else{ //일치
            completion.pop_back();
            participant.pop_back();
        }
    }
    
    return participant.back();

}