[프로그래머스/Python] 해시 - 완주하지 못한 선수(lv.1), 전화번호 목록(lv.2)

완주하지 못한 선수(lv.1)

문제보기

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

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

해시 맵으로 사용해봤다.

def solution(participant, completion):
    check = 0
    hmap = {}
    
    # 참가자들의 해시 저장
    for p in participant:
        hmap[hash(p)] = p
        check += int(hash(p))
        
    # 완주자들의 해시 값을 빼줌    
    for c in completion:
        check -= hash(c)
        
    # 완주하지 못한 사람의 해시값의 value 값을 빼줌
    return hmap[check]

파이썬의 hash(object)를 사용해봤다.

파이썬의 기본 내장함수인데, 객체의 해시가 있는 경우, 정수의 해시값을 돌려주는 함수이다. 딕셔너리 조회 중에 딕셔너리 키를 빨리 비교하는 데 사용되는데, 이때 해시 값이 같으면 숫자 값도 같다.

즉, 참가자(participant)의 해시값들을 딕셔너리에 저장해두고(key: 해시값, value: 참가자 이름), check 변수에 계속 더해준다. 그리고 check에서 완주자의 해시를 뺀다. 그럼 결국 완주하지 못한 한명의 해시값이 남는데, 이것을 딕셔너리에서 검색해서 해당 value값을 return 해주면 된다.

 

 

---

문제를 해결하고 다른 사람들의 코드를 봤는데 완전 심플하고 효율적인 코드를 찾았다.

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

collections 라이브러리를 가져와서 해결한 것인데, counter는 빼는 게 된다는 것을 처음 알아서 감탄하면서 봤다. 카운터를 사용하면 해당 리스트의 원소들이 몇 개 들어있는지 딕셔너리로 나타내준다. 그리고 이것들을 빼면 answer에는 {'완주하지 못한 참가자': 1}이 남는 것이다.

그래서 key 값의 첫번째 값을 가져오면 결과가 나온다.

 

 

---

전화번호 목록(lv.2)

문제보기

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

코딩테스트 연습 - 전화번호 목록

 

해시 문제인데 해시를 사용하지 않았던 문제

어떻게 진행할까 하다가 받아온 전화번호부를 오름차순으로 정렬하고, startswith를 사용해봤다.

# 내 코드
def solution(phone_book): 
    phone_book.sort()
    l = len(phone_book)
    for i in range(l):   
        for j in range(i+1, l):
            if phone_book[j].startswith(phone_book[i]):
                return False
    return True

만약 다른 번호로 시작하게 되면 false 리턴, 그렇지 않으면 true 리턴

그런데 결과는 효율성에서 두 개 틀림..ㅠㅠㅠ

보니까 for문을 두 개나 써서 그런 듯 해서, 이것 저것 찾아보다가 zip을 써보기로 했다.

# 변경한 코드
def solution(phone_book):
    phone_book = sorted(phone_book)
    for fst, sed in zip(phone_book, phone_book[1:]):
        if sed.startswith(fst):
            return False
    return True

zip을 사용해서 i, j로 나눌 것들을 하나로 합쳐봤다. 결과는 이렇게 하니 잘 돌아감!!

for을 두 개 써서 문제였던 게 확실해졌다

 

 

---

다른 사람 풀이도 봤는데 같은 방법이지만, 외부 라이브러리 사용때문에 잊어버릴까봐 공부겸 올려봤다.

from itertools import combinations as c
def solution(phone_book):
    # phone_book을 원소 길이를 기준으로 정렬
    phone_book = sorted(phone_book, key = len)
    for (a, b) in c(phone_book, 2):
         if a == b[:len(a)]:
                return False
    return True

phone_book 내부의 원소들을 길이 순서대로 정렬시키고, combinations 함수를 사용해서 2개씩 묶어준 뒤, 앞 글자가 같으면 False를 보내는 방법. 직관적이라 좋다고 생각했다.

풀이 과정은 나와 비슷하지만 방법이 달라서 적어봤다.