[프로그래머스 level1 완주하지 못한 선수]📌효율성 테스트 주의

오늘은 1단계 문제를 풀기 시작한 지 이틀된 날이다..!

오늘 문제를 풀면서 해시문제라고 되어 있던 문제를 가져와보았다.
(프로그래머스는 문제 푼 직후, 다른 사람들의 코드를 보며 배워가는 게 많은 사이트라는 걸 다시 느꼈다..🧸)

완주하지 못한 선수의 문제는 다음과 같다.
https://programmers.co.kr/learn/courses/30/lessons/42576

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

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

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

[입출력예]

participant	completion	return
["mislav","stanko","mislav","ana"]	["stanko","ana","mislav"]	"mislav"

 

 

 

우선, 처음에는 무조건 조건을 만족시키기 위해 무식하고 직관적이게 짰다.

(ver1)

def solution(participant, completion):
    for i in participant :
        if i in completion :
            completion.remove(i)
        elif i not in completion :
            return i

하지만 이럴 경우 partcipant 한 명 검사할 때마다 completion을 전체를 뒤져봐야 하므로 비효율적일 것 같았다.
어떻게 알았는지 딱 효율성 테스트를 통과하지 못하였다.

 

 

따라서, 배열을 정렬하고 배열의 순서와 다른 경우 그 사람은 완주하지 못한 것이므로 이러한 방법으로 접근하게 되었다.

(ver2)

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

이렇게 하였더니 효율성 테스트도 통과할 수 있었다..!

 

 

다른 사람들의 코드를 보며 많은 새로운 것을 알 수 있었어서 가져와보았다.

import collections

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

collections는 사용해본 적 없었기 때문에 기능을 찾아보았다.

collections.Counter()는 각 단어를 key로 단어가 나온 횟수를 value로 갖는 dictionary를 리턴해주었다.
이는 collections.Counter(participant) - collections.Counter(completion) 으로 차집합과 같이 처리할 수 있는 것 같았다.

이 문제에서 나왔던 해시는 key와 value 쌍으로 이루어진 데이터구조로 key로 데이터를 찾아 빠른 속도로 검색할 수 있게 한다. 파이썬에서 dictionary 구조와 상통하는 것 같다.

오늘 문제를 해결하면서 효율성을 위해서 할 수 있는 방법이 무엇인지 생각하는 힘을 더 길러야겠다는 것을 알 수 있었다. ⭐️