[알고리즘] 해시 - 완주하지 못한 선수

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

프로그래머스

 

Q. 
# 참가자, 완주자 2개의 array가 주어짐
# 참여자 수는 1<N<100,000
# 1명을 제외하고 모든 선수가 완주
# 이름은 1<n<20 알파벳 소문자
# 동명이인 존재할 수 있음
# 완주하지 못한 선수 이름 출력

---

필요한 개념/메소드
collections.Counter

: 주어진 iterable한 요소들이 각각 몇번 등장했는지 세어주는 도구

*딕셔너리와 유사하나, 특정 작업을 더 편리하게 수행할 수 있는 유용한 기능을 제공함

from collections import Counter

participants = ['john', 'doe', 'john', 'jane']
counter = Counter(participants)

# 딕셔너리와 유사한 형태
print(counter)
> Counter({'john':2,'doe':1,'jane':1})

# 대응되는 값 출력
print(counter('john'))
> 2

 
most_common() 메소드

print(counter.most_common(1))
> [('john', 2)]

 
subtract() 메소드

competers = ['john', 'jane']
counter.subtract(completers)

print(counter)
> Counter({'john':1, 'doe':1, 'jane':0})

 
연산

counter1 = Counter(['a','b','c','a'])
counter2 = Counter(['a','c','d'])

print(counter1 + counter2) 
> Counter({'a':3, 'c':2, 'b':1, 'd':1})

---

문제를 간단히 정리하면, “참가자와 완주자 리스트를 비교해서 없는 것 하나만 찾는 문제“

✅ 조건 정의

1. 참가자의 Counter 생성
2. 완주자의 리스트를 순회하며 Counter 값 차감
3. 남아있는 참가자 이름 중 값이 0이 아닌 이름 출력

A1. 

from collections import Counter

def solution(participant, completer):
    participant_counter = Counter(participant)
    for person in completer:
        participant_counter[person] -= 1
    for participant, count in participant_counter.items():
        if count > 0:
            return participant

A2. Counter객체 간의 차이 활용

• participant와 completion의 Counter를 구하고, 둘의 차를 구한 후 남아있는 Counter(완주하지 못한 선수)의 key값을 반환

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

A3. sort/loop를 사용한 방법

: 리스트를 정렬한 후, 같은 위치의 값들을 비교하는 방식 (인덱스가 일치하지 않을 경우, 완주하지 못한 선수)

*메모리 사용량이 적고, 직관적인 방식이나, 상대적으로 느릴 수 있음 (Counter 방식의 해시맵은 추가적인 메모리를 사용)

• participant, compeletion 리스트를 정렬 .sort()
• for 반복문을 통해 participant[i]와 completion[i]가 일치하는지 확인 (*completion 완주자의 len만큼 반복)

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i in range(len(completion)):
        if participant[i] != completion[i]:
            return participant[i]
    return participant[-1]

 

✅ 예외처리 (마지막 return문)
: 위의 코드는 완주자 기준이어서,

위와 같이 시작했을 경우, 완주자를 다 돌아도 완주하지 못한 선수를 찾을 수 없다.
→ 이를 위해 마지막에 participant[-1]을 반환하도록 수정

A4. 해시를 이용한 방법

• participant의 해시값을 딕셔너리에 저장하고, 합을 계산 (처음에 초기화 필요)
  • hash(part): 각 참가자의 이름을 hash값으로 변환
  • hashdict(hash(part) = part): hash값과 이름을 딕셔너리로 저장
  • sumhash += hash(part): 참가자들의 hash총합 계산
• 앞서 구한 합에서 completion의 해시 값을 차감
• 남은 해시 값의 key를 완주하지 못한 선수로 return

def solution(participant, completion):
    hashDict = {}
    sumHash = 0
    for part in participant:
        hashDict[hash(part)] = part
        sumHash += hash(part)
    for comp in completion:
        sumHash -= hash(comp)
    return hashDict[sumHash]

---

답변 비교

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

프로그래머스