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

프로그래밍/Python

donie 2020. 12. 3. 02:12

코딩테스트 연습 - 완주하지 못한 선수

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

programmers.co.kr

def solution(participant, completion):

hash = {}

for p in participant:

hash[p] = hash.get(p, 0) + 1

for c in completion:

hash[c] -= 1

ans = [k for k, v in hash.items() if v > 0]

return ans[0]

1) dictionary 자료구조

(1) 생성

Dict = {}

또는

Dict = dict(a=1, b=2, c=3)

(2) key값을 이용해 value찾기

Dict[key] : 이미 존재하는 key에 대한 value값 얻는 방법.

Dict.get(key, default) : 딕셔너리에 key가 있으면 해당 key에 대한 value를 반환하고, key가 없으면 default에 지정한 값을 반환하는 함수.

(3) 새로운 key 추가하기 or 기존 key의 value값 변경하기

Dict[key] = value

(4) 딕셔너리의 모든 key와 value를 튜플로 묶어서 반환하기

Dict.items()

(5) 특정 key값 삭제

del Dict[key]

2) 시간복잡도

participant의 모든 원소에 대해서 for loop -> O(N)

completion의 모든 원소에 대해서 for loop -> O(N)

딕셔너리의 items()함수: 딕셔너리의 모든 원소에 접근 -> O(N)

따라서 위 코드의 시간복잡도는 O(N + N + N) => O(N) 이다.