[묘공단] 코딩테스트 스터디 4주차
이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 8장 써머리입니다.
해시의 개념과 정의
키를 통해서 빠르게 데이터 탐색을 지원하는 자료 구조를 해시라고 한다
이 때 키를 만들 때 사용하는 함수를 해시 함수라고 하며 다음과 같은 특징이 있다
- 해시는 단방향으로 동작
- 상수 시간에 바로 찾을 수 있음
- 값을 인덱스로 활용하려면 적절한 변환 과정 필요
위와 같은 특징 중 단방향 동작을 활용한 비밀번호 관리, 상수 시간에 바로 찾을 수 있는 특징을 활용한 데이터베이스 인덱싱 그리고 블록체인에서 활용된다
해시 함수
파이썬에서는 딕셔너리 또는 셋 자료형을 통해 상수 시간에 키 검색이 가능하므로 직접 구현할 일은 많지 않다
그러나 직접 구현한다면 여러 가지 조건들을 고려해야하는 데
- 해시 함수의 변환 값을 키 (인덱스)로 사용하므로 해시 테이블의 크기를 넘으면 안된다
- 해시 함수의 변환 값 충돌을 최대한 적게 발생시켜야 한다
실제 구현은 소수와 나눗셈법, 곱셈법 등을 활용하여 만듬
충돌 처리
해시 함수의 충돌을 최소한으로 한다고해도 충돌은 언젠가는 발생하게 됨
아래와 같은 방식으로 충돌을 처리할 수 있다
- 체이닝을 통한 충돌 처리
- 오픈 어드레싱을 통한 충돌 처리
- 이중 해싱을 통한 충돌 처리
문제 풀이
두 개의 수로 특정값 만들기
문제 조건 중 중복되는 원소는 없다는 조건을 체크해야 함. 예를 들어 target이 10이고 element가 5일 때 diff는 5이므로 중복 원소 체크를 안하면 잘못된 결과가 나옴
from typing import List def solution(arr: List[int], target: int) -> bool: arr_set = set(arr) for element in arr: diff = target - element if diff in arr_set and diff != element: return True return False assert solution([1, 2, 3, 4, 8], 6) assert not solution([2, 3, 5, 9], 10)
문자열 해싱을 이용한 검색 함수 만들기
ord 함수는 매번 까먹어서 구글링하는데 기억을 해놓으면 좋을 듯 (아스키 문자에 대응하는 정수값)
문제 자체는 평이하나 hash 만드는 로직은 면접 때 자주 물어보는 소재 중 하나이므로 기억해두자
추가로 나머지 연산 시 (a + b) % m == (a % m + b % m) % m도 기억해놓을 것
from typing import List # hash(s) = (s[0] + s[1]*p + s[2]*p^2 ... s[n-1]*p^n-1) mod m # p = 31, m = 1,000,000,007 def hash_func(s: str) -> int: p = 31 m = 1_000_000_007 hash_val = 0 for index, char in enumerate(s): hash_val += (ord(char) * pow(p, index)) % m return hash_val % m def solution(string_list: List[str], query_list: List[str]) -> List[bool]: hash_string_set = {hash_func(s) for s in string_list} return [hash_func(s) in hash_string_set for s in query_list] assert solution( ["apple", "banana", "cherry"], ["banana", "kiwi", "melon", "apple"] ) == [True, False, False, True]
완주하지 못한 선수
동명이인 선수가 있으므로 단순히 set을 변경 후 diff로는 해결되지 않는다
참가자의 이름: 숫자 counter를 만들고 완주자 명단을 순회하면서 숫자 counter를 줄임
좀 신박한 풀이로는 participant와 completion을 모두 Counter 객체로 만들고 diff를 구하면 아주 쉽게 풀이 가능
from collections import Counter from typing import List def solution(participant: List[str], completion: List[str]) -> str: participant_counter = Counter(participant) for name in completion: participant_counter[name] -= 1 if participant_counter[name] == 0: participant_counter.pop(name) answer = [] for name in participant_counter.keys(): answer.append(name) return answer[0] assert solution(["leo", "kiki", "eden"], ["eden", "kiki"]) == "leo" assert ( solution( ["marina", "josipa", "nikola", "vinko", "filipa"], ["josipa", "filipa", "marina", "nikola"], ) == "vinko" ) assert ( solution(["mislav", "stanko", "mislav", "ana"], ["stanko", "ana", "mislav"]) == "mislav" )
할인 행사
해시 객체를 만들고 날짜별로 슬라이딩하면서 만족하는 지 체크하는 코드
flag를 이용해서 체크하는 로직이 중복되어있어서 리팩토링이 필요함
교재의 풀이와 큰 틀에서는 차이가 없는데 이게 O(N)인지는 바로 와닿지는 않음 :(
from collections import Counter from typing import List def solution(want: List[str], number: List[int], discount: List[str]) -> int: want_num_dict = {} for item, num in zip(want, number): want_num_dict[item] = num counter = Counter(discount[:10]) flag = True for k, v in want_num_dict.items(): if counter[k] < v: flag = False break answer = 1 if flag else 0 for i in range(len(discount) - 10): counter[discount[i]] -= 1 counter[discount[i + 10]] += 1 flag = True for k, v in want_num_dict.items(): if counter[k] < v: flag = False break answer = answer + 1 if flag else answer return answer
오픈채팅방
문제 설명만 잘 이해하면 쉽게 풀이할 수 있는 문제. user_id는 유니크하고 최종적으로 매핑되는 닉네임만 입력값을 순회하면서 해시테이블에 잘 업데이트하면 된다
from typing import List def _reformat_log_message(action: str, nickname: str) -> str: if action == "Enter": return f"{nickname}님이 들어왔습니다." else: return f"{nickname}님이 나갔습니다." def solution(record: List[str]) -> List[str]: nickname_by_user_id = {} logs_to_print = [] for row in record: logs = row.split(" ") action = logs[0] if action == "Enter": user_id, nickname = logs[1], logs[2] nickname_by_user_id[user_id] = nickname logs_to_print.append((action, user_id)) elif action == "Leave": user_id = logs[1] logs_to_print.append((action, user_id)) else: # Change user_id, nickname = logs[1], logs[2] nickname_by_user_id[user_id] = nickname answer = [] for action, user_id in logs_to_print: log_message = _reformat_log_message(action, nickname_by_user_id[user_id]) answer.append(log_message) return answer
베스트앨범
각 장르별 총 재생 횟수에 대한 정보와 각 장르에 속한 음원을 요구조건에 맞춰서 정렬 후 상위 2개만 뽑아내는 작업을 구현하면 쉽게 풀 수 있는 문제
from collections import defaultdict from typing import List def solution(genres: List[str], plays: List[int]) -> List[int]: play_by_genre = defaultdict(int) statistic_by_genre = defaultdict(list) for index, (genre, play) in enumerate(zip(genres, plays)): play_by_genre[genre] += play statistic_by_genre[genre].append((play, index)) sorted_genres = sorted( play_by_genre.keys(), key=lambda x: play_by_genre[x], reverse=True ) answer = [] for genre in sorted_genres: play_index_list = statistic_by_genre[genre] sorted_play_index_list = sorted(play_index_list, key=lambda x: (-x[0], x[1])) answer.extend([x[1] for x in sorted_play_index_list][:2]) return answer assert solution( ["classic", "pop", "classic", "classic", "pop"], [500, 600, 150, 800, 2500] ) == [4, 1, 3, 0]
신고 결과 받기
답안에 필요한 결과를 만들기 위해서 어떤 자료구조 (set, dict)를 사용할 지 잘 고려 하면 어렵지 않게 풀 수 있다
손으로 그려보는 게 중요한 것 같고, 조금 마음에 안드는 부분은 num_of_blocked_users를 구하는 부분인데 여기를 개선할 수 있으면 좋을 것 같음
from collections import defaultdict from typing import List def solution(id_list: List[str], report: List[str], k: int) -> List[int]: already_reported_logs = set() report_count_by_user_id = defaultdict(int) blocked_user_ids_by_user_id = defaultdict(list) for log in report: reporter, reported = log.split(" ") if (reporter, reported) in already_reported_logs: continue already_reported_logs.add((reporter, reported)) report_count_by_user_id[reported] += 1 blocked_user_ids_by_user_id[reporter].append(reported) answer = [] for user_id in id_list: num_of_blocked_users = len( [ x for x in blocked_user_ids_by_user_id[user_id] if report_count_by_user_id[x] >= k ] ) answer.append(num_of_blocked_users) return answer
메뉴 리뉴얼
Counter의 most_common을 사용하면 중간 부분의 max_num 가지고 처리하는 부분을 깔끔하게 해결할 수 있음
from collections import defaultdict from itertools import combinations from typing import List def solution(orders: List[str], course: List[int]) -> List[str]: answer = [] for r in course: count_by_course_combinations = defaultdict(int) for order in orders: for combination in combinations(order, r): count_by_course_combinations["".join(sorted(combination))] += 1 combination_count = count_by_course_combinations.values() if not combination_count or max(combination_count) < 2: continue max_num_of_combinations = max(combination_count) answer.extend( [ x for x in count_by_course_combinations.keys() if count_by_course_combinations[x] == max_num_of_combinations ] ) return sorted(answer) assert solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4]) == [ "AC", "ACDE", "BCFG", "CDE", ] assert solution(["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2, 3, 5]) == [ "ACD", "AD", "ADE", "CD", "XYZ", ] assert solution(["XYZ", "XWY", "WXA"], [2, 3, 4]) == ["WX", "XY"]
의상
첫 번째 테스트케이스에서 시간 초과 나는 코드, 조금 더 고민해보고 안되면 힌트를 봐야할 것 같음
현재 구현은 단순히 요구하는 대로 조합을 계산하면서 캐싱된 값이 있으면 그걸 최대한 활용하게 구현함
from collections import defaultdict from itertools import combinations from typing import List def solution(clothes: List[List[str]]) -> int: count_by_clothes_type = defaultdict(int) for row in clothes: _, clothes_type = row count_by_clothes_type[clothes_type] += 1 answer = sum(count_by_clothes_type.values()) cache = {(k,): v for k, v in count_by_clothes_type.items()} clothes_type = count_by_clothes_type.keys() for i in range(2, len(clothes_type) + 1): for combination in combinations(clothes_type, i): cache_result = cache.get(combination[:-1]) num_of_combinations = cache_result * count_by_clothes_type[combination[-1]] answer += num_of_combinations cache[combination] = num_of_combinations return answer assert ( solution( [ ["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"], ] ) == 5 ) assert ( solution( [["crow_mask", "face"], ["blue_sunglasses", "face"], ["smoky_makeup", "face"]] ) == 3 )
압축
한 글자만 남았을 때와, next_word가 마지막 케이스일 때 예외처리 때문에 좀 지저분하게 작성함
다른 사람 풀이를 보면 좀더 neat하게 작성할 수 있음, 아이디어 자체는 딕셔너리 활용 문제에 가까움
from typing import List def solution(msg: str) -> List[int]: answer = [] compression_dict = { str(char): ord(char) - 64 for char in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" } current_index, last_index = 0, 26 while current_index < len(msg): current_word = msg[current_index] if current_index == len(msg) - 1: answer.append(compression_dict[current_word]) break for i in range(current_index + 1, len(msg)): next_word = f"{current_word}{msg[i]}" if next_word in compression_dict: if current_index + len(next_word) == len(msg): answer.append(compression_dict[next_word]) current_index += len(next_word) break else: current_word = next_word continue else: answer.append(compression_dict[current_word]) compression_dict[next_word] = last_index + 1 last_index += 1 current_index += len(current_word) break return answer
폰켓몬
프로그래머스 해쉬 추가 문제. 문제 지문과 예시만 잘 읽어보면 어처구니 없을 정도로 쉽게 풀이 가능한 문제
굳이 조합이니 뭐니 찾을 필요가 없음
from typing import List def solution(nums: List[int]) -> int: possible_num_of_choices = len(nums) // 2 return min(len(set(nums)), possible_num_of_choices)
전화번호 목록
해쉬 카테고리에 있지만 정렬로 우선 풀이. 풀고 나니 Trie를 써야하는 문제인 것 같기도 함
다른 풀이로도 한 번 풀어볼 것
from typing import List def solution(phone_book: List[str]) -> bool: sorted_phone_book = sorted(phone_book) index = 0 while index < len(phone_book) - 1: if sorted_phone_book[index + 1].startswith(sorted_phone_book[index]): return False index += 1 return True assert not solution(["119", "97674223", "1195524421"]) assert solution(["123", "456", "789"]) assert not solution(["12", "123", "1235", "567", "88"])
반응형
댓글
이 글 공유하기
다른 글
-
[묘공단] 코딩테스트 스터디 6주차
[묘공단] 코딩테스트 스터디 6주차
2023.12.30 -
[묘공단] 코딩테스트 스터디 5주차
[묘공단] 코딩테스트 스터디 5주차
2023.12.22 -
[묘공단] 코딩테스트 스터디 3주차
[묘공단] 코딩테스트 스터디 3주차
2023.12.08 -
[묘공단] 코딩테스트 스터디 2주차
[묘공단] 코딩테스트 스터디 2주차
2023.11.30
댓글을 사용할 수 없습니다.