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

문제

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

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

<제한사항>

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

 

내가 생각한 풀이 방법

두 배열 모두 오름차순으로 정렬한다

이중 for문을 돈다.

첫 번째 for문에서는 참가자들 한 명 한 명에 접근

두 번째 for문에서는 완주자들 한 명 한 명에 접근하여

만약 완주자 명단에 같은 이름이 있다면 continue

같은 이름이 없다면 해당 이름을 answer에 할당한다

 

아니면 for문 하나만 돌아서 참가자 한 명 in 완주자 명단

이렇게 하는 게 더 효율적인가?

 

그동안 코드실행을 눌러봐야하는 지 모르고 제출 후 채점으로 성패를 확인했다

그랬더니 내 점수가 완전 하위권,,

앞으로는 코드실행으로 확인해보고 제출하자ㅠㅠ

 

코드로 구현

1차 시도

def solution(participant, completion):
    answer = ''
    parti = sorted(participant)
    compl = sorted(completion)
    for i in parti:
        for j in compl:
            if i == j:
                continue
            else:
                answer = j
    return answer

- 잘못 생각했다.. 인덱스가 달라버리면 (예를들어 중간에 하나가 빠졋다(=그 사람이 미완주자)라던가) 그냥 else로 빠져나간다

 

2차 시도

def solution(participant, completion):
    answer = ''
    parti = sorted(participant)
    compl = sorted(completion)
    for i in parti:
        if i in compl:
            continue
        else:
            answer = i
    return answer

- 결과로 빈 문자열은 왜 나오는 것인가?

     → mislav가 두 명인데 앞 mislav에서 그냥 continue 시켜버려서 그렇다!

 

2차 시도

def solution(participant, completion):
    answer = ''
    parti = sorted(participant)
    compl = sorted(completion)
    for i in parti:
        if i in compl:
            compl.remove(i)
        else:
            answer = i
    return answer

- 있는지 확인만 하는 게 아니라 그냥 없애버리기

- 정확성 테스트는 통과했는데 효율성 테스트에서 탈락 ㅠㅠ

 

3차 시도

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

- index를 사용하지 않으면 처음에 sort 해준게 의미가 없을 것 같아서(?) index를 활용해봤는데 바로 성공..!

- 아무래도 시간 복잡도를 비교해봐야할 것 같다

다른 사람 풀이

이 문제는 특히나 다른 사람들의 풀이가 중요했다.

왜냐하면 이건 해시 문제였기 때문이다

나느 해시 관련 코드를 한번도 짜 본 적이 없다.

이 기회로 해시 코드를 짜봐야겠다.

https://velog.io/@matisse/%EC%99%84%EC%A3%BC%ED%95%98%EC%A7%80-%EB%AA%BB%ED%95%9C-%EC%84%A0%EC%88%98-python

python | 완주하지 못한 선수

https://jione-e.tistory.com/44

[프로그래머스] Level1 - 완주하지 못한 선수 (Python)

https://mgyo.tistory.com/177

[프로그래머스] 완주하지 못한 선수 문제 풀이(해시 Lv.1) - 파이썬 Python