문제 링크 및 문제 내용

코딩테스트 연습 - 완주하지 못한 선수 | 프로그래머스 (programmers.co.kr)

문제 설명

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

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

제한사항

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

입출력 예

participant	completion	return
["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

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

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

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

출처

풀이 코드

# 처음 풀이코드
def solution(participant, completion):
    #참가자 반복문
    for i in participant:
				#해당 참가자가 완료자 중에 있을경우 완료자 명단에서 삭제하게 하였습니다.
				#동명이인의 참가자의 경우를 대비
        if i in completion:
            completion.remove(i) #remove 시간 복잡도 0(N)
        #참가자가 완료자 명단에서 없을 경우 리턴
        else:
            return i

처음에 이 문제를 풀때 중복 인물이 있을 경우에 처리가 까다로워 remove를 써야겠다고 접근했습니다.
하지만 정확도에서는 통과했지만 시간이 초과되었습니다 ㅠㅠ

코테를 준비한지 얼마 안되기 때문에 시간복잡도에 대한 중요성에 대해 모르고 있었습니다.

remove의 시간복잡도는 O(N)이었고, 다른 방향을 생각 해봐야 했고,
구글링 결과 set이나 dict의 경우에는 모두 O(1)의 시간 복잡도를 갖고 있다는 것을 확인 하였고 dict으로 접근해봐야겠다는 생각이 들었습니다.

# dict을 사용한 풀이 코드
def solution(participant,completion):
    dict = {}
    # 반복문을 통해 참가자 명단 딕셔너리 생성
    for name in participant:
				# 해당 키값이 있을 경우 밸류 값 + 1
        if dict.get(name):
            dict[name] += 1
        # 해당 키값이 없을 경우 밸류 값 1을 주어주고 생성   
        else:
            dict[name] = 1
    # 반복문을 통해 완주자 명단에서 같은 키값(이름)의 밸류 -1            
    for name in completion:
            dict[name] -= 1
           
    #키 값중 1 이상이면 리턴             
    for key in dict:
        if dict[key] > 0:
            return key

# 번외 충격받은 코드

import collections

def solution(participant,completion):
	 #collections의 counter 함수로 이렇게 쉽게 가능했다..
	 #count 함수는 해당 리스트의 중복을 체크해서 키값 밸류값을 나누어 준다.
     	 #저런식으로 객체간의 빼기가 가능하다는 점..
	 answer = collections.Counter(participant) - collections.Counter(completion)
	 retuer list(answer.keys())[0])

출력

테스트 1입력값 〉["leo", "kiki", "eden"], ["eden", "kiki"]
기댓값 〉"leo"
실행 결과 〉테스트를 통과하였습니다.
테스트 2입력값 〉["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"]
기댓값 〉"vinko"
실행 결과 〉테스트를 통과하였습니다.
테스트 3입력값 〉["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]
기댓값 〉"mislav"
실행 결과 〉테스트를 통과하였습니다.

실행 시간

효율성  테스트
테스트 1 〉통과 (22.79ms, 21.7MB)
테스트 2 〉통과 (35.93ms, 25.3MB)
테스트 3 〉통과 (40.12ms, 27.6MB)
테스트 4 〉통과 (49.19ms, 34MB)
테스트 5 〉통과 (48.77ms, 33.9MB)

후기

저에게는 시간 복잡도라는 중요한 부분을 깨닫게 해주는 문제였습니다.
삽입, 제거, 탐색, 포함 여부 확인등의 연산이 필요할 때
List 자료형보다 Set이나 Dict 자료형의 사용을 지향해야겠다는 생각이 들었습니다!