01 완주하지 못한 선수 - 풀이

2022.03.25 - [알고리즘/커뮤러닝] - 01 완주하지 못한 선수

01 완주하지 못한 선수

위 문제의 접근법과 최적의 풀이법을 살펴보자!

 

체크 

- 동명이인 > 이름이 주어지면 몇번이나 배열에 등장했는지 체크 필요

 

자료구조 : 알고리즘에 따라 적합한 자료구조 사용

- 이름 대신 번호가 주어지면 : 선형 배열 - 인덱스를 통해 해당 번호의 완주여부 체크

- 이름이 주어지면 : 문자열로 접근할 수 있는 자료구조가 필요 = 해시 (딕셔너리)

 

✅ 해시 : Key-Value

{'leo':'1', 'kiki':'1', 'eden':'1'} 

- 해시 테이블을 통해 Key와 Value가 Mapping 됨

- hash Function 필요 : 같은 칸에 Mapping 될 수도 있음

= Collision (충돌) : Bucket을 여러개 사용하여 해결

 

Python -> dictionary

: O(1) 접근 가능

---

풀이

1. participant에서 각 이름의 등장 횟수 Count, hash로 기록

2. completion에서 각 이름의 count 감소 시킴

3. 해시의 이름 중에 count가 0이 아닌 사람 = 완주하지 못한 선수임

 

내 풀이방법

def solution(participant, completion):      # 참여 선수들, 완주한 선수들
    answer = ''     # 완주하지 못한 선수의 이름
    p = {}
    c = {}

    # 동명이인 체크를 위해 각 참가자 별 인원 체크 - 딕셔너리 사용
    for item in participant:
        if p.get(item) :
            p[item] += 1
        else:
            p[item] = 1

    # 동명이인 체크를 위해 각 참가자 별 인원 체크 - 딕셔너리 사용
    for item in completion:
        if c.get(item) :
            c[item] += 1
        else:
            c[item] = 1

    # 참가자 딕셔너리에 없거나, 각 딕셔너리의 Value 값이 다르면 완주 X
    for item in participant:
        if item not in c.keys():
            answer = item
            break
        elif p[item] != c[item]:
            answer = item
            break

    return answer

✅ 개선점

- 딕셔너리 변수를 두개나 사용할 필요가 없다.

---

풀이 💯

def solution(participant, completion):
	answer = ''
    
    # 1. 딕셔너리에 각 이름 별 participant 인원 count
    for x in participant:
    	d[x] = d.get(x, 0) + 1	# 처음 등장하는 이름이면 1, 아니면 1 증가
     
    # 2. 완주한 참가자 수 감소
    for x in completion:
    	d[x] -= 1
    
    # 3. 완주하지 못한 선수 출력 : 1인 값
    dnt = [k for k, v in d.items() if v > 0]	# value가 0이 아닌 이름을 리스트로 추출
    
    answer = dnt[0]		# 완주하지 못한 선수는 1명
    
    return answer

- 복잡도

: participant loop 1개, completion loop1개

* 리스트 컴프리헨션 : 딕셔너리의 크기에 비례하는 연산 (Loop)

-> 해시의 복잡도가 O(1)이기 때문에 배열의 크기에 비례

= O(n) 

 

* 정렬을 활용한 풀이 : 복잡도에서 큰 차이는 없지만 해시를 사용하는게 효율성이 더 좋다.

# 정렬을 이용한 방법
def solution(participant, completion):
	# 1. 참가자와 완주자의 이름순 정렬
	participant.sort()
    completion.sort()
    
    # 2. Loop로 이름 비교 : 다를 경우 완주 못한 사람임 - 미 완주자는 한명이기 때문
    for i in range(len(completion)):
    	if participant[i] != completion[i]:
        	return participant[i]	# 완주 못한 사람
            
    return participant[-1]	# 마지막으로 남은 선수 = 완주하지 못한 선수

- 복잡도 : 배열 정렬 O(nlogn), completion Loop O(n)

= O(nlogn)

 

+ 타 수강생의 조언

- 딕셔너리에 값을 넣을 때 이미 그 키가 존재하는지 확인하는 조건문을 줄이기 위해서 defaultdict을 제안했다

- 이런게 있는 줄도 몰랐다 ㅜ 다른 언어만 너무 써서 파이썬의 편리함을 못 누리는 중

* defaultdict 

: 딕셔너리의 기본값을 설정한다 defaultdict(int)를 하면 기본값이 0으로 세팅됨

-> 다음에 사용법 자세히 포스팅 하기로 하자

from collections import defaultdict

def solution(participant, completion):
    d = defaultdict(int)

    for p in participant:
        d[p] += 1
    
    for c in completion:
        d[c] -= 1

    for name, count in d.items():
        if count != 0:
            return name

- 복잡도 : O(n)으로 동일

 

 

가독성도 그닥, 쓸데없는 변수 사용 등으로 부족한 점이 많았지만 그래도 해결 했다는 점 칭찬한다