Level1. 완주하지 못한 선수

jeeyeonLIM commented 3 years ago

문제 설명

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

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

제한사항

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

입출력 예

입출력 예 설명

예제 #1

leo는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2

vinko는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3

mislav는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

jeeyeonLIM commented 3 years ago

나의코드

def solution(participant, completion):
    #answer = ''
    for i in completion[:]: 
        participant.remove(i)
    return participant[0]

효율성 전부 통과못했다.
참가자 중에는 동명이인이 있을 수 있습니다. 이것 때문에 어찌 해야할지..
난관
for문을 두번 돌려서 리스트 두개를 모두 검사하면서 제외할 생각만 했다.
if i in그렇다고 한들 중복되는 경우가 모두 삭제되기 때문에 answer 에는 빈값만이 들어오게 되는 방식이 되었다.
for + remove 함께 사용할때 에러난다. for i in 리스트[:] 형태로 써줘야 한다.
del 사용하면 제외할때마다 제외되지 않은 list가 print됨.

jeeyeonLIM commented 3 years ago

모범답안

Ver1. Sort 활용

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

sort 속도가 빠르다. 오름차순 하고 반복되는 경우 or participant 에만 있는 경우 해당 값을 추출할 수 있다.
만약 위 step1 에서 값이 return되지 않는다면 participant 맨 뒤에 있는 사람이 완주하지 못한 경우에 해당하므로 마지막 값을 추출한다.
참고 : https://wooaoe.tistory.com/71
대다나다 ❗

Ver2. index 활용 (효율성 Test X)

def solution(participant, completion):
    for x in completion:
        participant.pop(participant.index(x))
    return participant[0]

간결하다.
participant.index("leo") : completion 내에 있는 "leo" 값과 같은 값을 가진 participant 의 index를 가져온다. ❗ 단, 값이 중복되어 존재하는 경우, 맨 처음 등장한 문자의 인덱스를 출력하게 되므로, 중복된 값은 자동 배제되게 된다.
participant.pop(participant.index(x)) : index에 해당하는 participant값 제외하게 된다.
참고코드 : https://jeonzzang.tistory.com/10?category=954636
헛.. 다만 효율성 테스트는 통과하지 못한다ㅠㅠ

jeeyeonLIM commented 3 years ago

Ver3. Collections Counter 이용

from collections import Counter
def solution(participant, completion): 
    answer = Counter(participant) - Counter(completion) 
    return list(answer.keys())[0]

아래와 같이 Counter 사용하면 갯수 세준다.
각각에 대응되는 갯수를 빼주면 된다.

jeeyeonLIM commented 3 years ago

정통 Hash 활용하기

jeeyeonLIM commented 3 years ago

다시풀기

예전처럼 sort, sort 후 값 비교해가는 방식으로 풀었다.

def solution(participant, completion):
participant.sort()
completion.sort()
for i in range(len(completion)): # 개수가 1개 더 작은 completion크기만큼 돌릴거야
    if participant[i] != completion[i]: # 만약 같은 index에 값이 다르다면 
        return participant[i]           # 참가자 중 한명을 고를거야
return participant[-1]                  # 끝날때까지 return되는 게 없으면 participant의 맨 마지막 값일것임.

Hash 활용한다면 ❗ ❗ ❗ ❗

다른사람들 풀이 : collections 모듈 활용하기

collections.Counter(리스트 넣어줄거) : 이렇게 사용하면 dict형태로 바꿔준다.

import collections
def solution(participant, completion):
# print(collections.Counter(participant))
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]

내풀이 : 직접 해시맵 생성하고, 완주자기준 검사해서 value값 변화시켜가기. 마지막에 key <-> value 처리 후 값 찾기

def solution(participant, completion):

    # 해시맵 생성 - 참가자 기준으로
    part_hash = {}
    for i in participant:
        if i not in part_hash.keys():
            part_hash[i] = 1
        else :
            part_hash[i] += 1

    # 완주자 기준 검사해주기
    for i in completion:
        if i in part_hash.keys():
            part_hash[i] -= 1 # 

    # value로 key찾기 (value=1인 key가져오기)
      #  -> 이건 두가지 방법이 있어서 아래 첨부함. value로 key 찾기 방법 찾아봤는데 아래 두개가 베스트인듯.
    # method1. items + list comprehension
    key = [k for k,v in part_hash.items() if v == 1]
    return ''.join(key) # ['leo'] 형태를 'leo' 형태로 바꿔주려고

    # method2. key <-> value 뒤집은 dictionary 만들기
    reverse_dict = {v:k for k,v in part_hash.items()}
    return reverse_dict[1]

jeeyeonLIM / coding_test