[Programmers, Lv.1] 코딩테스트 고득점 Kit - 해시 (1) (Python)

1. 폰켓몬 (Level 1)

---

(문제 설명, 제한사항, 입출력 예)

폰켓몬의 종류 번호가 담긴 1차원 배열 nums가 주어진다.
연구실에 있는 총 N 마리의 폰켓몬 중에서 박사님이 N/2마리를 가져가도 좋다고 말했을 때,
가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아 그때의 폰켓몬 종류 번호의 개수를 구하라는 문제이다.
(가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 구하면 된다.

 

(내가 생각한 풀이 과정)

중복되지 않는 경우의 수를 골라야 가장 많은 폰켓몬 종류를 가져갈 수 있는 것이니, 일단 중복을 제거해 주기 위해 집합 set을 사용했다.

기존 nums 리스트에 중복값이 없다고 가정했을 때는, nums/2 만큼이 최대 종류로 가져갈 수 있는 경우이다.
만약, 중복값이 존재하는 (즉, nums/2 보다 set(nums)의 길이가 짧은) 경우에는 집합 nums의 길이가 최대 종류로 가져갈 수 있는 경우의 수가 되겠다.

 

(코드)

💡 내 코드

def solution(nums):
    if len(set(nums)) > len(nums)/2: return len(nums)/2
    else: return len(set(nums))

 

💡 다른 사람의 풀이 코드

나와 같은 풀이 코드를 한 줄로 요약했다.
굳이 조건을 나누지 않고, nums/2의 길이와 set(nums)의 길이를 비교해서 둘 중 최소값을 반환하는 식으로도 구현이 가능하다.

def solution(ls):
    return min(len(ls)/2, len(set(ls)))

 

---

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

---

(문제 설명, 제한사항, 입출력 예)

단 한 명의 선수를 제외하고 모든 선수가 완주한 마라톤 시합이 있다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때,
완주하지 못한 선수의 이름을 구하라는 문제이다.
(반드시 completion 리스트의 길이는 participant 리스트의 길이보다 1 작으며, 참가자 중에는 동명이인이 있을 수 있다고 한다.)

 

(내가 생각한 풀이 과정 #1 - 반복문과 조건문을 사용)

처음에는 어렵지 않게 생각했다.
participant 리스트의 요소를 한 번씩 반복하면서, completion 리스트의 해당 요소를 삭제한다.
만약, completion 리스트에 해당 반복 element가 존재하지 않으면, 해당 선수가 마라톤에서 완주하지 못한 것으로 생각할 수 있다.

-> 반복문이 하나밖에 없다는 점에서 그리 큰 시간 복잡도가 걸리지 않을 것이라 생각했지만, 런타임 에러가 뜨게 된다.

 

(내가 생각한 풀이 과정 #2 - sorted 이용 코드)

정렬하는 알고리즘, sorted를 이용하는 방법도 있었다.

participant와 completion 리스트 각각을 모두 정렬시키고, 두 요소를 zip으로 묶어서 반복시켰을 때 두 값이 같지 않는다면 해당 participant의 참가자가 마라톤을 완주하지 못했을 것이다.
만약 모두 반복이 끝났는데 반환되지 못했다면, 반복문을 돌지 못한 participant의 마지막 요소가 완주하지 못했을 것이다.

 

(내가 생각한 풀이 과정 #3 - 해시 이용 코드)

이번 단원이 해시 단원인 만큼, 해시 테이블을 이용해서 문제를 해결할 수도 있었다.

participant를 반복시키면서, 딕셔너리에 "hash Key: participant element" 형식으로 값을 추가해 준다. 이때 원하는 값을 찾기 위해, 별도의 sumHash라는 변수를 만들어 Key값을 계속 더해준다.
이렇게 딕셔너리가 만들어진 후, 이제는 completion을 반복하면서 sumHash의 Key 값을 계속 빼준다.
마지막으로 남은 sumHash 정수값이 완주하지 못한 선수의 Value를 담고 있는 Key값이 될테니, 찾아주면 문제를 해결할 수 있겠다.

-> 두 번의 반복을 시켜도, Hash의 데이터 저장, 찾기 성능이 뛰어나 런타임 에러가 발생하지 않은 것을 확인할 수 있었다. 

 

(코드)

💡 #1. 문제 풀이 코드

#1. 런타임 에러 코드
def solution(participant, completion):
    for pl in participant:
        if pl in completion: 
            completion.remove(pl)
        else:
            return pl

 

💡 #2. 문제 풀이 코드

# 2. sorted 이용 코드 (성공)
def solution(participant, completion):
    participant = sorted(participant)
    completion = sorted(completion)
    
    for i, j in zip(participant, completion):
        if i!=j: return i
    return participant[-1]

 

💡 #3. 문제 풀이 코드

# 3. 해시 이용 코드 (성공)
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]