Level1 완주하지 못한 선수 (c++, python)

완주하지 못한 선수

LEVEL 1

https://programmers.co.kr/learn/courses/30/lessons/42576?language=cpp

문제 풀이 (효율성 X)

단순하게 생각하면 됩니다.

1. 완주선수 목록에서 string을 하나씩 꺼낸다.
2. 참가자 목록에서 찾아서 지운다.
3. 마지막으로 남은 한 명의 이름을 참가자 목록에서 출력한다.

하지만 이는 효율성 테스트를 통과하지 못합니다.
우선 최대 100,000번 for문을 반복합니다
그리고 cpp의 find를 이용해 찾게되면 제일 끝에 있다면 100,000 찾아봐야 될 수도 있습니다
즉 O(n^2 + n) = O(n^2) 이 걸릴 것으로 예상됩니다 (n은 vector::erase의 time complexity)

문제 풀이 (효용성 O)

우선 sorting을 한 후에 진행합니다

1. 앞에 부터 차례대로 비교해 나갑니다
2. 그러다가 이름이 다르다면 그 사람은 바로 완주자 목록에 없는 사람입니다(동명이인인데 완주자가 아닐 수도 있음. 3번 예제)
3. 찾았으므로 바로 완주하지 않은 사람 찾기 종료
   이는 예제를 직접 정렬해본 채로 따라가보면 바로 알 수 있습니다
   딱 한 명만 차이가 나기 때문에 가능합니다
   시간 복잡도는 O(n) 입니다.

 

위 풀이에서 틀린 부분이 있다면 지적 감사합니다~~

 

Git

https://github.com/wlgh325/Programmers_algorithm/tree/master/Level1/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80%20%EB%AA%BB%ED%95%9C%20%EC%84%A0%EC%88%98

GitHub - wlgh325/Programmers_algorithm: 프로그래머스 알고리즘 c++, 자바 풀이

 

c++ 코드

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

using namespace std;

string solution(vector<string> participant, vector<string> completion) {
    string answer = "";

    sort(participant.begin(), participant.end());
    sort(completion.begin(), completion.end());

    for (int i = 0; i < completion.size(); i++) {
        if (completion[i] != participant[i]) {
            return participant[i];
        }
    }
    return participant.back();
}

python 코드

def solution(participant, completion):
    answer = ''

    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if participant[i] == completion[i]:
            continue
        else:
            answer = participant[i]
            return answer

    answer = participant[len(participant) -1]

    '''
    for i in completion:
        if i in participant:
            participant.remove(i)

    answer = participant[0]
    '''


    return answer