[프로그래머스] 완주하지 못한 선수(해시 Lv.1)

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

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

 

 

개념

파이썬에서 해시(hash)는 딕셔너리 라는 자료구조로 구현할 수 있다.

해시는 언제 사용하는 것이 좋을까??

>>  1. 인덱스 값을 숫자가 아닌 다른값으로 사용하려고 할 때(리스트에서는 원소접근시 list['a']가 불가능하다) 

>>  2. 빠른 접근과 탐색이 필요할때

 

리스트와 딕셔너리의 시간복잡도를 비교하면 아래 사진과 같다.

Dictionary가 List에 비해 빠른 시간복잡도를 갖고 있기에, 원소를 삭제,추가 등이 많을 때에는 딕셔너리를 사용하는 것이 효율적이다. 

시간복잡도 비교

1. get메소드 : 딕셔너리에서 원소를 가져오는 방법이다. 

get(key,x) 의 형태로 사용한다. 

딕셔너리에 key값이 없는경우, x(디폴트값)를 리턴해주면 된다. 

 

for i in participant:
        d[i] = d.get(i, 0) + 1  

        # 주어진 키 i가 존재하면 그 값을, 없으면 0(디폴트값)

i가 존재하면 그 값을 리턴해 인원수를 +1해주고, 없다면 0에 +1을 해준다는 의미이다. 

 

 

2. 딕셔너리로 for문 조회하기

2-1. key로만 조회하는 방법

dict = {'apple' : 2, 'banana' : 5, 'grape' : 0}

for key in dict:

      print(key)

 

2-2. items()를 사용해 key, value로 동시 조회하기

for key, value in dict.items():      print(key, value)

 

혹은 

 

result = [k for k, v in dict.items() if v == 0] 

 

3. 딕셔너리 key값 삭제하기 del dict[key]

dict = {'apple' : 2, 'banana' : 5, 'grape' : 0}

del dict['apple']

 

 

 

코드

 

처음에 푼 풀이이다. 시간초과가 떠서 실행이 되지 않았다. 

# 처음 풀이 : 돌아가긴 하나 시간초과 뜸
def solution(participant, completion):
    answer = ''
    for c in completion:
        if c in participant:
            participant.remove(c)
    return participant[0]

 

 

해시(딕셔너리)를 사용해서 풀면 효율적으로 풀 수 있다. 

# 해시 : 이름을 키로 사용, 동명이인의 수를 값
def solution(participant, completion):
    d={}  # 빈사전
    for i in participant:
        d[i] = d.get(i, 0) + 1  # 주어진 키 i가 존재하면 그 값을, 없으면 0(디폴트값)을
        # 처음 등장하면 0+1, 동명이인이라면 기존인원수+1

    for j in completion:
        d[j] -= 1  # 이름 한명씩 빼주기
    result = [k for k, v in d.items() if v>0]  # value가 1인 선수 찾기
    answer = result[0]
    return answer