프로그래머스 알고리즘 / 해시 기초

프로그래머스 알고리즘 / 해시 기초

2022. 3. 1. 01:53ㆍ카테고리 없음

https://programmers.co.kr/learn/courses/30/lessons/42576?language=python3

완주하지 못한 선수

문제 설명

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

마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.

제한사항

마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.

입출력 예participantcompletionreturn

["leo", "kiki", "eden"]	["eden", "kiki"]	"leo"
["marina", "josipa", "nikola", "vinko", "filipa"]	["josipa", "filipa", "marina", "nikola"]	"vinko"
["mislav", "stanko", "mislav", "ana"]	["stanko", "ana", "mislav"]	"mislav"

입출력 예 설명

예제 #1
"leo"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #2
"vinko"는 참여자 명단에는 있지만, 완주자 명단에는 없기 때문에 완주하지 못했습니다.

예제 #3
"mislav"는 참여자 명단에는 두 명이 있지만, 완주자 명단에는 한 명밖에 없기 때문에 한명은 완주하지 못했습니다.

출처

----

def solution(participant, completion):
    answer = list(set(participant) - set(completion))
    return answer[0]

가장 간단하게 생각 - 동명이인 문제 해결 x

def solution(participant, completion):
    answer = ''

    participant.sort()
    completion.sort()

    for i in range(len(completion)):
        if(participant[i] != completion[i]):
            return participant[i]

    return participant[len(participant)-1]

1. list sorting

2. len(completion) 만큼 participant를 비교함

3. 전부 돌아도 없는 경우에는 마지막이 완주하지 못한사람 [-1]

---- 남의 풀이

3. collections 모듈

https://programmers.co.kr/learn/courses/30/lessons/42576/solution_groups?language=python3&type=all

import collections


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

1) Counter 이해하기 (출처 https://coding-grandpa.tistory.com/85)

Python이 제공하는 collections 라는 모듈의 한 class이다.
list를 가지고 Counter를 생성하면, Counter는 Key가 이름이고, Value가 count 인 dictionary를 반환하게 된다.

2) participant / completion 배열을 Counter로 변환하기

위와 동일한 방식으로 completion list도 Counter로 만들 수 있다.

3) participant와 completion 배열 간의 차 구하기

collections.Counter(participant) - collction.Counter(completion)
- Counter class는 상호간의 뺄셈 연산을 지원한다.
- 즉, 뺄셈 연산 한번으로 둘 participant는 있고, completion에는 없는 사람을 찾을 수 있다.

4) 마지막 Counter에서 Key값을 읽어오기

3) 단계의 결과는 dictionary 로 나오는데, 이 중 우리는 Key를 꺼내와야 한다.
- list(answer.keys())[0]
- answer로 부터 Keys를 꺼내온다
- Keys를 list로 형변환 하고
- 이 중 0번 째 인덱스의 값을 읽어온다
위 동작을 수행하고 나면 {"A" : 1} 이라는 Dict로부터 ["A"] 라는 list를 꺼내오게 되고, 여기서 [0] 으로 접근하면 "A"라는 String을 꺼내오게 된다.
이를 반환하면 정답이 된다.

4. Hash 를 사용

출처: https://coding-grandpa.tistory.com/85

def solution(participant, completion):
    hashDict = {}
    sumHash = 0 
    
    # 1. Hash : Participant의 dictionary 만들기 
    # 2. Participant의 sum(hash) 구하기 
    for part in participant:
        hashDict[hash(part)] = part 
        sumHash += hash(part)
        
    # 3. completion의 sum(hash) 빼기 
    for comp in completion: 
        sumHash -= hash(comp) 

    # 4. 남은 값이 완주하지 못한 선수의 hash 값이 된다 
    return hashDict[sumHash]

1) HashMap 만들기

HashMap이란 Key-Value의 Pair를 관리하는 클래스이다.
이 문제에서 Key는 hash한 값이 되겠고, Value는 각 선수의 이름으로 해둔다.

2) HashMap에 Participant 추가하기

'Hashing을 한다'라고도 표현하는데, HashMap에 Participant를 전부 추가해보자.
이 문제에서는 각 이름의 Hash 값을 구하고, 이 값들의 합을 구한다.

3) sumHash에서 완주한 선수의 Hash값 빼기

sumHah에서 완주자들을 제외시키면, 한 명만 남게 될 것이고 그 사람이 우리가 찾는 정답일 것이다.

4) Value가 0이 아닌 참가자 찾기

이쯤 되면 문제가 다 해결됐다고 볼 수 있다.
남아있는 1명이 ~~마피아~~완주하지 못한 사람이니, sumHash == 5인 Key를 갖고 있는 사람을 찾으면, 완주하지 못한 선수가 나온다.
그래서 hashDict[sumHash] 라는 코드가 나오게 된다.

728x90

저작자표시 비영리 (새창열림)

ParkParksu