[프로그래머스] 완주하지 못한 선수 Python 풀이

프로그래머스(Programmers) 완주하지 못한 선수 문제

난이도 : Level 1

<문제 링크>

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

프로그래머스

 

각 리스트를 반복하면서 participant에서 completion를 빼줬다

def solution(participant, completion):

    answer = ''

    for i in completion:

        if i in participant:

            participant.remove(i)

    answer = ''.join(participant)

    return answer

답을 맞췄지만 시간초과 이슈발생,,,,,, 

 

집합 자료형(set)을 활용해서 요소 접근을 빠르게 해보자 

차집합(-)을 활용했더니 participant에 동명이인이 있는 경우 실패.... 

def solution(participant, completion):

    answer = ''

    p = set(participant)

    c = set(completion)

    answer =list(p - c)

    return ''.join(answer)

 

요소에 빠르게 접근하면서 동명이인 문제를 해결할 수 있는 방법은 없는 것일까....

이름과 등장횟수를 기록한 딕셔너리 구조를 통해 해결 (Hash 알고리즘 이용) 

-> 딕셔너리 구조를 이용해 key값으로 요소에 빠르게 접근 가능, 이름과 등장횟수를 기록하며 동명이인 문제 해결 

def solution(participant, completion):

    answer = ''

    # 빈 딕셔너리 생성

    dic= {}    

    # 참가자 이름과 등장횟수만큼 기록 (동명이인 방지)

    for i in participant:

        if i in dic:

            dic[i] += 1

        else:

            dic[i] = 1

    # 참가지 딕셔너리에 완주자 이름이 등장하면 등장횟수 1씩 뺌

    for j in completion:

        dic[j] -= 1

    # 참가자 딕셔너리에 0이 아닌경우 답

    for name , cont in dic.items():

        if cont != 0:

            answer = name

    return answer