완주하지 못한 선수

완주하지 못한 선수
알고리즘 대회에 참여를 신청한 사람 이름이 담긴 배열 participate와 시험에 불참하지 않고 응시한 인원 이름이 담긴 배열 completion이 존재한다. 단 한사람만을 제외하고 모두 시험에 참여했다고 할 때, 불참한 인원의 이름을 return하도록 작성하라

• 신청한 사람의 수는 1명 이상 100000명 이하
• completion 길이는 participate의 길이보다 1 작다.
• 참가자의 이름은 1개 이상, 20개 이하의 알파벳 소문자로 이루어져 있다.
• 참가자 중에는 동명이인이 있을 수 있다.

풀이 과정

자료 구조의 선택

이름 대신 번호가 주어졌다면 선형 배열(linear array)를 사용해서 문제를 해결할 수 있지만, 현재는 번호 대신 문자열이 주어졌기 때문에, 배열 대신 문자열로 접근할 수 있는 "해시"를 사용하는 것이 좋아보인다.

해시(Hash)

해시 사용의 이유

리스트를 쓸 수 없을 때
인덱스 값을 숫자가 아닌 다른 값 '문자열, 튜플'을 사용하려고 할 때 딕셔너리를 사용하면 좋다.

빠른 접근 / 탐색이 필요할 때
딕셔너리 함수의 시간복잡도는 대부분 O(1)이므로 빠른 자료구조이다.

집계가 필요할 때
원소의 개수를 세는 문제가 많이 출제된다.
이때 해시와, collections 모듈의 Counter 클래스를 사용하면 빠르게 문제를 풀 수 있다.

코드

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

코드 해석

dic = {}  # dictionary를 생성한다

for person in participant:
    dic[person] = dic.get(person, 0)+1 # dic에 person을 키값으로 가지는 값을 가져오고, 값이 없다면 값을 0으로 초기화
									   # 가져온 값에 1을 더해서 dic[person]에 대입

for person in completion:
    dic[person] -=1 # completion에 있는 값을 dic의 키값으로 이용해서 값을 -1
    # 이 과정을 통해 dic에는 참가하지 않은 사람 1명만이 '1'의 값을 가지게됨 / 나머지는 0

dnf = [k for k, v in dic.items() if v > 0]
# "k for k"는 리스트 컴프리헨션에서 결과값으로 저장할 요소를 정의하는 부분
# 여기서는 딕셔너리의 키(k)를 저장하도록 지정

# items() 메서드는 딕셔너리(dic)의 키-값 쌍을 반환하는 이터레이터를 생성
# 생성된 이터레이터는 (키, 값)의 튜플을 차례대로 반환

# 딕셔너리의 키-값 쌍을 순회하는 부분은 "for k, v in dic.items()" / 키(k)와 값(v)을 각각 변수에 할당하여 순회

# if 조건문인 "if v > 0"은 값(v)이 0보다 큰 경우에 해당하는 키(k)를 선택하는 조건
# 조건을 만족하는 경우, 선택된 키(k)가 리스트 컴프리헨션의 결과값으로 저장

# 최종적으로, 리스트 컴프리헨션은 딕셔너리(dic)의 키-값 쌍을 순회하면서 값이 0보다 큰 경우에 해당하는 키(k)를 리스트(dnf)에 저장

dnf 리스트에는 딕셔너리(dic)에서 값이 0보다 큰 키(k)들이 저장되어 반환된다.
이는 딕셔너리에서 등장 횟수가 0보다 큰 요소들의 목록을 나타낸다.

추가로 공부해봐요

hash function, hash collision

체육복

체육복
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

풀이 과정

자료 구조의 선택

학생이 모두 번호로 나와있으니 배열을 선택한다.

코드

def solution(n, lost, reserve):
    lostAndReserve = set(lost) & set(reserve)
    realLost = set(lost) - lostAndReserve
    realReserve = set(reserve) - lostAndReserve
    for x in sorted(realReserve):
        if x - 1 in realLost:
            realLost.remove(x-1)
        elif x + 1 in realLost:
            realLost.remove(x + 1)
    return n - len(realLost)

코드 해석

lostAndReserve = set(lost) & set(reserve) # 도둑맞고 여벌도 가지고있는 학생 / 교집합
realLost = set(lost) - lostAndReserve # 도둑맞고 여벌은 없는 진짜 없는 학생들 / 차집합
realReserve = set(reserve) - lostAndReserve # 여벌을 가지고있는데 도둑은 안맞은 학생들 / 차집합

for x in sorted(realReserve): # 진짜 여벌 있는 학생만큼 반복
	if x - 1 in realLost: # 학생 번호 -1의 번호를 가지고 있는 학생이 realLost(진짜 잃어버린 학생) 에 존재한다면
		realLost.remove(x-1) # realLost 에서 학생 번호 -1 번호를 가지고 있는 학생을 realLost에서 삭제
    elif x + 1 in realLost: # x + 1로 같은 과정
    	realLost.remove(x + 1)

return n - len(realLost) # 전체 학생수 - 진짜 잃어버린 학생 수 = 체육시간에 참가 가능한 학생 수

헷갈렸던 점

for문을 돌 때 여분 체육복을 가진 학생이 도둑맞은 친구들한테 체육복을 빌려주는 과정인데, 빌려주고 나면 여분 체육복이 없다고 명시해줘야 하는거 아닌가? 생각했다.
하지만 for문을 돌리면 조건에 맞으면 다시 여분의 체육복을 가진 학생이 빌려줘야 할 일이 없으므로 remove를 안해줘도 괜찮다.