프로그래머스-완주하지 못한 선수

문제설명

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
• completion의 길이는 participant의 길이보다 1 작습니다.
• 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
• 참가자 중에는 동명이인이 있을 수 있습니다.

입출력의 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

예제 #1
- "leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #2
- "vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.
예제 #3
- "mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

나의 접근1

해시 문제라길래 해시로 접근해서
일단 딕셔너리 구조로 접근

def solution(participant, completion):
    # 딕셔너리생성
    hash_table={}
    cnt = 0
    for i in range(len(participant)):
        if participant[i] in hash_table:
            while True:
                if participant[i] + str(cnt) in hash_table:
                    cnt +=1
                else:
                    hash_table[participant[i] + str(cnt)] = participant[i]
                    break
        else:
            hash_table[participant[i]] = participant[i]
    # 딕셔너리에 값이 있는지 확인하고 비교하려 했으나 보류
    # answer = ''
    # for i in participant:
        # if i not in completion:
            # answer += i
    # return answer

이런식으로 코드를 짜려구 했으나 코드가 너무 복잡해져서 보류 하고 다른 접근

나의 접근2

해시 구조에 대한 생각보다는 다른방법으로라도 문제를 풀어보자라는 생각
전체 선수 리스트에서 완주자를 빼서 나온 값을 리턴해보자 라고 접근

def solution(participant, completion):
    for i in completion:
        participant.remove(i)
    return ','.join(participant)

정답은 잘 출력이 되지만 효율성 테스트에서 모든 문제 오답이 나버림

나의 접근3

리스트를 정렬한 후에 반환하는 함수를 만든다면 속도가 조금이나마 빨라지지 않을까 라고 접근함

def solution(participant, completion):
    participant.sort()
    completion.sort()
    answer = ''
    for i in range(len(completion)) :
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

정렬을 한다고 해도 효율성문제는 해결되지 않음

나의 접근4

지금까지 못봤던 제한사항의
completion의 길이는 participant의 길이보다 1 작습니다
이 문구를 보고
완주 하지 못한 선수는 1명이 라는것을 파악
완주하지 못하는 선수를 만나면 더이상 탐색을 하지 않는 코드를 만들자 라고 접근
전체 선수와 완주 선수를 정렬해서 비교해보자 라고 접근

def solution(participant, completion):
    participant.sort()
    completion.sort()
    answer = ''
    for i in range(len(completion)) :
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

정답!!