[파이썬] 프로그래머스 커뮤러닝 1주차 완주하지 못한 선수

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

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

 

- 제한사항

 1. completion 의 길이는 participant 보다 짧다는 것을 알 수 있음

 2. N에 비례하는 복잡도를 가지는 Linear 타입의 알고리즘임

 3. 집합을 보고 차집합을 구하면 되는 문자라는 것을 볼 수 있음

 

- 자료구조

 1. 만약 이름 대신 번호가 주어졌다면? -> 선형배열(linear array)

 2. 배열을 사용하여 가능한 모든 조합의 수를 나타내려고 하면, 26의 20승의 배열을 잡아서 진행해야 되므로 시간초과가 뜰것임

 3. 즉, 해시(Hash)를 사용하여 풀어야 되는 문제임 

해시란?

 - 위의 그림은 7개의 칸의 테이블이 있고, 사람들의 이름을 key로 하여 이 안에 값을 저장하는 것을 해시라고 부르며, 저장공간을 해시 테이블이라고 한다. leo는 2번째, eden은 3번째, kiki는 마지막에 매핑되었다. 각각 해당하는 값을 들어가도록 만듬

 - 해시 테이블 내에 각각 칸을 해시 버킷 이라고 하며, 값이 다를 수록 해시 펑션을 가지고 진행함

 - 만약에 서로 다른 키가 같은 값을 가르키는 것을 충돌이라고 부르는데, 충돌이 될경우, 이를 반드시 해결해야 함

 - 값에 또다른 값을 추가하여 서로 구분할 수 있도록 해야 함 

 

문제의 풀이

 - "mislav"에 1을 대입하고, "stanko"를 1을 대입 또 "mislav"에 1을 대입하여 2를 만들고, "ana"에 1을 대입함

 - 여기서 completion배열을 보면 "stanko"배열을 보면 1이 빼주고 되고 "ana" 1이 빼주고  되고 "mislav"값 1 을 빼준다.

그러면 "mislav"가 1이 남게 된다. 즉 1이 남는 사람이 완주하지 못한 사람이다.

 

 

직접 먼저 풀어보기

def solution(participant, completion):
    participant.sort()
    completion.sort()
    for i,v in zip(participant, completion):
        if i != v:
            return i
    return participant.pop()

  - 해시 즉, dict로 풀려다 제대로 작동하지 않아서 구글링을 통해 코드를 참고하였다.

  - 먼저 둘의 값을 .sort()로 정렬해준다 그리고 zip 함수를 이용하여 둘의 값을 병렬로 묶어서 for문을 사용하였다.

  - 정렬이 되었으므로 각 값이 서로 대응될 것이다. 만약 대응되지 않는다면 그 값이 완주하지 못한 선수이름 일 것이다.

  - 이름이 같은 값이 있다면 배열의 값이 하나 남을 것이므로 pop함수를 통해 retrun 해준다.

 

정답강의

def solution(participant, completion):
    d = {}
    for x in participant:
        d[x] = d.get(x, 0) + 1
    for x in completion:
        d[x] -= 1
    
    dnf = [k for k, v in d.items() if v>0]
    answer = dnf[0]
    return answer

 - d라는 빈 dict를 만들고 participant를 첫번째 for문을 통해 get 매서드를 통해서 d.get(x,0)을 활용해 x가 존재하면 그 값을, 존재하지 않으면 0을 리턴하도록 한다.

 - completion을 for문을 통해서 해당하는 키값이 있으면 1씩 빼주도록 한다.

 - dnf는 리스트 컴리헨션을 사용하여 d.items을 통해 키,밸류 를 나타내고, v가 0이 아닌 값이면, 그 키값을 넣어주도록 한다. 그리고 answer을 리턴하도록 만든다.

 

 - 나의 풀이처럼 정렬을 활용해서 풀어도 통과는 하겠지만, 문제의 요점은 해시를 이용해서 키를 이용해서 알고리즘의 복잡도를 linear code를 이용하는 것보단 해시를 활용해서 푸는게 옳다.