Python 코딩 테스트 학습 기록
해시는 값을 빠르게 찾기 위한 자료구조다. 해시의 원리와 딕셔너리, 집합, Counter를 활용하는 문제 18~25를 정리한다.
해시의 기본
해시는 값을 일정한 규칙으로 계산해 저장 위치를 찾는 방법이다. 파이썬의 dict와 set은 해시를 이용한다. dict는 키에 값을 연결하고, set은 중복 없이 존재 여부를 확인하며, Counter는 값별 개수를 센다.
서로 다른 값이 같은 해시값을 갖는 충돌은 가능하다. 파이썬의 집합과 딕셔너리는 충돌이 생겨도 실제 값을 다시 비교해 구분한다. 따라서 문자열 검색에서는 해시값만 따로 저장하기보다 문자열 자체를 집합에 넣는 편이 안전하다.
문제 18. 두 개의 수로 특정값 만들기
배열에서 서로 다른 두 원소를 골라 더했을 때 target을 만들 수 있는지 확인한다. 현재 수가 num이면 필요한 짝은 target - num이다.
처음 접근과 한계
def solution(arr, target):
hash = [0] * (target + 1)
for num in arr:
if num <= target:
hash[num] = 1
for num in arr:
if num >= target:
continue
if target - num == num:
continue
if hash[target - num]:
return True
return False인덱스로 존재를 표시한 방법이다. 다만 hash는 내장 함수 이름과 겹치고, 음수·큰 수에는 쓰기 어렵다. 더 중요한 예외는 [3, 3], 6이다. 같은 수 두 개가 필요해도 target - num == num을 건너뛰면 정답을 놓친다.
기본 풀이: set
def solution(arr, target):
seen = set()
for num in arr:
if target - num in seen:
return True
seen.add(num)
return False현재 수를 넣기 전에 필요한 짝을 확인한다. 원소 하나를 두 번 쓰지 않으며, 첫 번째 3을 저장한 뒤 두 번째 3을 만나면 참을 반환한다.
범위가 작고 음수가 없을 때의 대안
def solution(arr, target):
present = [0] * (target + 1)
for num in arr:
needed = target - num
if 0 <= needed <= target and present[needed]:
return True
if 0 <= num <= target:
present[num] += 1
return False문제 19. 문자열 해싱 검색
문자 코드의 단순 합은 순서가 다른 "act"와 "cat"도 같은 값으로 만들 수 있다. 이전 결과에 소수 31을 곱하고 문자를 더하면 순서가 계산에 반영된다.
def polynomial_hash(text):
p = 31
m = 1_000_000_007
hash_value = 0
for char in text:
hash_value = (hash_value * p + ord(char)) % m
return hash_valueord(char)는 문자를 숫자로 바꾸고, 나머지 연산은 값이 지나치게 커지는 것을 막는다. 다항 해시도 충돌 가능성은 남는다.
안전하고 간단한 검색
def solution(string_list, query_list):
strings = set(string_list)
return [query in strings for query in query_list]해시값을 리스트에 넣고 찾으면 순차 탐색이 된다. 문자열 자체를 집합에 넣으면 빠른 검색과 충돌 구분을 함께 얻는다. 매개변수 이름으로는 내장 이름 str보다 text가 좋다.
문제 20. 완주하지 못한 선수
동명이인이 있으므로 집합이 아니라 이름별 개수를 세야 한다.
def solution(participant, completion):
counts = {}
for name in participant:
counts[name] = counts.get(name, 0) + 1
for name in completion:
counts[name] -= 1
for name, count in counts.items():
if count > 0:
return namedict.get(name, 0)은 처음 나온 이름에는 0을 준다. 완주자를 만날 때마다 1씩 빼면 양수로 남은 이름이 답이다.
Counter 풀이
from collections import Counter
def solution(participant, completion):
remaining = Counter(participant) - Counter(completion)
return next(iter(remaining))Counter끼리 빼면 남은 개수만 유지된다. 짧은 코드는 위의 개수 세기 원리를 이해한 뒤 쓰는 편이 좋다.
문제 21. 할인 행사
원하는 상품과 수량이 연속된 10일 할인 목록과 정확히 맞는 시작일을 센다.
def solution(want, number, discount):
wanted = dict(zip(want, number))
answer = 0
for start in range(len(discount) - 9):
ten_days = {}
for item in discount[start:start + 10]:
if item in wanted:
ten_days[item] = ten_days.get(item, 0) + 1
if ten_days == wanted:
answer += 1
return answerrange(len(discount) - 9)은 마지막 10일 구간까지 포함한다. 길이가 14라면 시작점 4에서 인덱스 4~13을 확인한다. get(item, 0)은 처음 나온 상품을 0개에서 시작하게 하므로 KeyError를 막는다.
Counter 풀이
from collections import Counter
def solution(want, number, discount):
wanted = Counter(dict(zip(want, number)))
return sum(
Counter(discount[start:start + 10]) == wanted
for start in range(len(discount) - 9)
)문제 22. 오픈채팅방
사용자가 나중에 닉네임을 바꾸면 이전 입장·퇴장 기록에도 마지막 닉네임이 적용된다. 따라서 첫 번째 순회에서 아이디별 최종 닉네임을 만들고, 두 번째 순회에서 메시지를 만든다.
def solution(record):
nickname = {}
for line in record:
command = line.split()
if command[0] != "Leave":
nickname[command[1]] = command[2]
answer = []
for line in record:
command = line.split()
action, user_id = command[0], command[1]
if action == "Enter":
answer.append(f"{nickname[user_id]}님이 들어왔습니다.")
elif action == "Leave":
answer.append(f"{nickname[user_id]}님이 나갔습니다.")
return answersplit()은 공백을 기준으로 문자열을 나눈다. Change는 출력할 사건이 아니므로 두 번째 순회에서 메시지를 만들지 않는다.
문구를 분리한 풀이와 문자열 형식
def solution(record):
nickname = {}
message = {
"Enter": "님이 들어왔습니다.",
"Leave": "님이 나갔습니다."
}
for line in record:
command = line.split()
if command[0] in ("Enter", "Change"):
nickname[command[1]] = command[2]
answer = []
for line in record:
command = line.split()
action, user_id = command[0], command[1]
if action != "Change":
answer.append(nickname[user_id] + message[action])
return answer예전 문자열 형식인 "%s님" % name에서 %s는 문자열 자리다. 현재는 변수 이름이 보이는 f"{name}님"이 읽기 쉬워 자주 사용한다.
문제 23. 베스트앨범
장르별 총 재생 수가 큰 순서로 장르를 고르고, 각 장르에서는 재생 수가 큰 노래를 최대 두 곡 고른다. 재생 수가 같으면 고유번호가 작은 곡이 먼저다.
def solution(genres, plays):
songs_by_genre = {}
total_plays = {}
for index, (genre, play) in enumerate(zip(genres, plays)):
if genre not in songs_by_genre:
songs_by_genre[genre] = []
total_plays[genre] = 0
songs_by_genre[genre].append((index, play))
total_plays[genre] += play
ordered = sorted(total_plays.items(), key=lambda item: item[1], reverse=True)
answer = []
for genre, _ in ordered:
songs = sorted(songs_by_genre[genre], key=lambda song: (-song[1], song[0]))
answer.extend(index for index, _ in songs[:2])
return answerkey=lambda song: (-song[1], song[0])은 재생 수 내림차순, 고유번호 오름차순이라는 두 정렬 기준을 표현한다. append([4, 1])는 [[4, 1]]처럼 리스트 하나를 넣고, extend([4, 1])는 [4, 1]처럼 원소를 각각 넣는다. 여기서는 정답 목록에 번호를 차례대로 넣어야 하므로 extend가 맞다.
defaultdict 대안
from collections import defaultdict
def solution(genres, plays):
songs_by_genre = defaultdict(list)
total_plays = defaultdict(int)
for index, (genre, play) in enumerate(zip(genres, plays)):
songs_by_genre[genre].append((index, play))
total_plays[genre] += play
answer = []
for genre in sorted(total_plays, key=total_plays.get, reverse=True):
songs = sorted(songs_by_genre[genre], key=lambda song: (-song[1], song[0]))
answer.extend(index for index, _ in songs[:2])
return answerdefaultdict(list)는 처음 보는 장르에 빈 리스트를, defaultdict(int)는 0을 자동으로 준비한다.
문제 24. 신고 결과 받기
같은 사람이 같은 사용자를 여러 번 신고해도 한 번으로 처리해야 한다. 신고당한 사람을 키로 두고 신고자를 집합에 넣으면 중복이 자연스럽게 사라진다.
def solution(id_list, report, k):
reporters_by_user = {}
for line in report:
reporter, reported = line.split()
if reported not in reporters_by_user:
reporters_by_user[reported] = set()
reporters_by_user[reported].add(reporter)
mail_count = {}
for reporters in reporters_by_user.values():
if len(reporters) >= k:
for reporter in reporters:
mail_count[reporter] = mail_count.get(reporter, 0) + 1
return [mail_count.get(user_id, 0) for user_id in id_list]결과 순서는 id_list 순서여야 하므로 마지막에도 그 목록을 순회한다. 메일을 받지 못한 사용자는 get(user_id, 0)으로 0을 넣는다.
defaultdict 대안
from collections import defaultdict
def solution(id_list, report, k):
reporters_by_user = defaultdict(set)
mail_count = defaultdict(int)
for line in report:
reporter, reported = line.split()
reporters_by_user[reported].add(reporter)
for reporters in reporters_by_user.values():
if len(reporters) >= k:
for reporter in reporters:
mail_count[reporter] += 1
return [mail_count[user_id] for user_id in id_list]문제 25. 메뉴 리뉴얼
각 주문에서 코스 길이만큼 가능한 메뉴 조합을 만들고, 가장 많이 주문된 조합을 고른다. 두 명 이상이 주문한 조합만 후보가 된다.
from collections import Counter
from itertools import combinations
def solution(orders, course):
answer = []
for length in course:
candidates = []
for order in orders:
candidates.extend(combinations(sorted(order), length))
counts = Counter(candidates)
if not counts:
continue
max_count = max(counts.values())
if max_count >= 2:
for combo, count in counts.items():
if count == max_count:
answer.append("".join(combo))
return sorted(answer)sorted(order)가 중요하다. "WX"와 "XW"를 모두 ('W', 'X')라는 같은 조합으로 세기 때문이다.
Counter(candidates)는 조합별 횟수를 센다.counts.values()는 횟수만,counts.items()는 조합과 횟수를 함께 꺼낸다."".join(combo)는('A', 'C')를"AC"로 잇는다. 빈 문자열은 사이에 구분자를 넣지 않는다는 뜻이다.
공동 1위가 여러 개면 모두 넣어야 하므로 count == max_count를 사용한다. 마지막 sorted(answer)는 답을 사전순으로 정렬한다.
해시 문제 체크리스트
- 존재 여부만 필요하면
set을 먼저 떠올린다. - 값별 개수가 필요하면
dict.get또는Counter를 쓴다. - 중복을 없애야 하면 집합을 사용한다.
- 결과 순서가 정해져 있으면 원래 순서 목록을 기준으로 답을 만든다.
- 정렬 조건이 여러 개면
key=lambda x: (첫째 기준, 둘째 기준)처럼 튜플로 쓴다. - 중복, 마지막 구간, 동점, 빈 결과를 확인한다.
마무리
해시는 딕셔너리 문법 자체보다 “무엇을 키로 저장하면 다음 판단이 쉬워질까?”를 묻는 사고방식에 가깝다. 존재 확인은 집합으로, 횟수 비교는 딕셔너리와 Counter로, 중복 제거는 집합으로 해결한 흐름을 반복해서 확인해 보자.