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

1. 문제

programmers.co.kr/learn/courses/30/lessons/42576

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

2. 소스코드 (Python3)

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]

 

3. 고찰

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) 이다.