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

iamjinseo·2022년 8월 17일

문제풀이-Python

목록 보기

46/134

문제

수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

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

시도

1

def solution(participant, completion):
    answer = ''
    #https://vision-ai.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%A6%AC%EC%8A%A4%ED%8A%B8-count-%EC%99%80-len
    #https://security-nanglam.tistory.com/427
    dic = {p:participant.count(p) for p in participant} #참가자 이름인 사람이 몇 명 있는지 세기
    for c in completion:
        dic[c]-=1
        if dic[c] == 0:
            del dic[c]
    # print(dic.keys())
    return list(dic)[0]
    # for d, i in dic.items(): #키, 값 모두  https://dojang.io/mod/page/view.php?id=2308
    #     if i>0:
    #         return d

dic = {p:participant.count(p) for p in participant} #참가자 이름인 사람이 몇 명 있는지 세기
: 참가자 이름을 키값으로, 그 이름의 인원수를 밸류로 받은 딕셔너리 생성함.

for c in completion:
        dic[c]-=1
        if dic[c] == 0:
            del dic[c]

: 완주자 이름 하나당 딕셔너리에서 해당 이름 가진사람의 인원수 밸류 감소
: 인원수가 0이되면 딕셔너리에서 제거
return list(dic)[0]
: 마지막 남은 딕셔너리의 리스트를 반환

결과

실패!

2

하는 수 없이 구글링을 하기로 함.
구글링으로 찾아낸 결과에 의하면

참가자와 완주자를 정렬하고,

참가자와 완주자를 zip으로 묶음

한 쌍 안에서 이름이 다르면 반환, 모두 같을 경우에는 참가자의 마지막 사람 반환

근데 이건 해시가 아닌데?ㅠㅠㅠ 난 해시로 풀고 싶다.

3

딕셔너리로 해결한 다른 분의 코드를 봤는데, 내 알고리즘이랑 크게 다르지 않다.

그러나 조금 다른 부분이 있었는데, 그 분은 밸류값(인원수)을 반복문으로 넣었다. 나는 count로 해결했는데. (dic = {p:participant.count(p) for p in participant} #참가자 이름인 사람이 몇 명 있는지 세기)

따라서 이 부분을 고쳐보기로 했다.

    # 참가자 이름인 사람이 몇 명 있는지 세기
    # 이름:인원수
    for p in participant:
        if p in dic:
            dic[p] += 1 
        else:
            dic[p] = 1

결과

오예
사용 공간 측면에서 효율성을 본 것 같다. (아닐수도)

해설

구글링하면 이런 저런 풀이법이 많이 나오지만 문제 유형은 해시이므로 해시답게 접근하는 편이 좋다.

{참가자이름:인원수} 딕셔너리 생성
참가자 participant에서 for 문 돌리면서 해당 이름의 인원수를 +1 한다. (없으면 새로 만들어준다)
완주자 completion 에서 for 문 돌리면서 해당 이름의 인원수를 -1 한다.
밸류값이 0이 되면 딕셔너리에서 없애버린다.
마지막 남은 키값이 곧 미완주자이므로 반환한다.
5-1. 반환할 때는 딕셔너리를 리스트로 만들어 0번 인덱스를 반환하도록 한다.

코드

def solution(participant, completion):
    dic = {} # 참가자와 인원수 딕셔너리
    
    # 참가자 이름인 사람이 몇 명 있는지 세기
    # 이름:인원수
    for p in participant:
        if p in dic:
            dic[p] += 1 
        else:
            dic[p] = 1
    
    for c in completion:
        dic[c]-=1
        if dic[c] == 0:
            del dic[c]
    return list(dic)[0]