이 글은 골든래빗 <코딩 테스트 합격자되기 파이썬편>의 8장 써머리입니다.
[해시 기본 개념]
저장 규칙을 안다면 순차탐색으로 인한 비효율 해결 可.
즉, 해시함수와 key값을 통해 특정 규칙으로만 자료 검색 -> 시간복잡도 O(1)
key값으로 value를 검색하는 구조이지만, value로 key값을 찾을 수 없다는 특징이 있다.
bucket(버킷): hash table의 각 데이터
실제 사용처: 비밀번호 관리, db indexing, 블록체인 등.
코딩테스트에서는 데이터 탐색이 많을 때 시간복잡도를 줄이기위해 해시를 고려한다.
[해시함수]: 대표 예제(이론;기본 지식이다!)
해시함수는 다른값을 넣었을 때 다른 값이 나오도록 유도하는 목적이다. (같은 값 나오면 충돌을 의미)
1. 나눗셈법(division method): key(x)를 소수(k)로 나눈 나머지를 인덱스 정보로 사용 -> 해시 테이블 크기 = k
모듈러 연산 = 나머지를 취하는 연산 (모듈러 k를 취한다 = k로 나눈 나머지를 취한다)
* 모듈러 1을 취한다 = 정수를 제외한 소수 부분만 취한다.
소수 쓰는 이유: 다른 수와의 충돌을 줄이기 위함
단점: 큰 데이터 사용시, 큰 소수가 필요한데, 큰 소수를 구하는 효율적 방법이 없어서 기계적 방법으로 구해야 함
2. 곱셈법(multiplication method): ((xA) mod 1) m) where A = golden ration(황금비) and m = 해시 테이블 크기
황금비(=A) = 약 1.6180339887... ~> 임의 길이 2등분할 때, 전체:긴 = 긴:짧 이 되는 것.
연산법: (key * A) 에서 모듈러 1 취함 (소수만 취함) -> 이 값에 테이블 크기 m을 곱하고 그 값으로 해시 테이블에 매핑
-> 나눗셈법과 달리 소수가 필요없다는 장점이 있음
3. 문자열 해싱: 문자열 자료에 대응하기위한 방법, 문자열 -> 다항식의 계수로 변환.
메르센 소수(=p) = 2^n - 1 숫자 중 소수인 수. 해시 충돌을 효과적으로 줄인다는 연구결과 有. ex) 31
연산법: 문자열에 대응되는 숫자에 p^index값 을 곱한 값을 각 문자별로 저장 후 전부 더하고 해시테이블 크기 m으로 모듈러 연산
문제점: 단순 문자열도 모듈러 연산 전까지 값이 굉장히 커짐 -> 각 문자열마다 모듈러연산을 하면서 연산으로 개선(오버플로 방지)
[충돌(collision)처리]: 서로 다른 key에 대해 결괏값이 같은 상황을 처리해야 함
1. 체이닝: 해당 버킷에 Linked list로 같은 해시값을 가지는 데이터 연결. 가장 간단한 방법
문제점: if 충돌 多 -> linked list 길이↑ -> 검색 성능↓ & 다른 해시 테이블 공간 덜 사용 -> 공간 활용성↓
2. 개방주소법(open addressing): 빈 버킷을 찾아 충돌값 삽입 -> 체이닝보다 메모리 효율적 사용
선형 탐사(linear probing): 충돌 발생 -> 다른 빈 버킷을 찾을 때까지 일정한 간격(보통은 1)으로 이동
문제점: 빈 버킷에 넣으면 결국 충돌한 값끼리 모이는 영역(cluster)형성 문제.
-> 이를 방지하기 위해 제곱수만큼 이동하여 탐사하기도 함.
이중 해싱: 해시 함수 2개 사용. 2번째 함수는 충돌 발생시 해당 위치 기준으로 충돌값 위치를 결정하는 용도가 됨.
[해시 실전 문법]
python에서는 딕셔너리(dict) 자료형을 사용하면 된다. 키와 값을 매핑하는 과정이 중요하다.
특정 값이나 정보를 기준으로 빈번한 검색이 필요하거나 관계를 확인하는 작업이 문제에 있다면 해시를 고려한다.
문제 18) 두 개의 수로 특정값 만들기
합이 target인 두 수가 arr에 있는지 찾고 있으면 True, 없으면 False가 나와야합니다.
for문을 돌리는 방법(완전 탐색)이 있지만, 이를 쓰면 시간복잡도는 O(N^2)이다.
# 문제는 타겟값이 나올 수 있는지 없는지 유무이다. 해시를 쓰지 않은 답안
def solution1(arr, target):
for i in arr:
value = target - i
if value != i and 0 <= value <= target and value in arr:
return True
return False
assert solution1(arr1:=[1, 2, 3, 4, 8], target1:=6) == True, '출력값1 에러'
assert solution1(arr2:=[2,3,5,9], target2:=10) == False, '출력값2 에러'
아이디어: 원소의 유무를 표시하는 해시 테이블을 만든다. (저자의 풀이)
def count_sort(arr, k):
# ➊ 해시 테이블 생성 및 초기화
hashtable = [0] * (k + 1)
for num in arr:
# ➋ 현재 원소의 값이 k 이하인 때에만 처리
if num <= k:
# ➌ 현재 원소의 값을 인덱스로 해 해당 인덱스의 해시 테이블 값을 1로 설정
hashtable[num] = 1
return hashtable
def solution(arr, target):
hashtable = count_sort(arr, target)
for num in arr:
complement = target - num
# ➍ target에서 현재 원소를 뺀 값이 해시 테이블에 있는지 확인
if (
complement != num
and complement >= 0
and complement <= target
and hashtable[complement] == 1
):
return True
return False
문제 19) 문자열 해싱을 이용한 검색 함수 만들기
문자열이 있으면 True, 없으면 False가 나와야합니다.
저자의 풀이이다.
# ➊ polynomial hash를 구현한 부분
def polynomial_hash(str):
p = 31 # 소수
m = 1_000_000_007 # 버킷 크기
hash_value = 0
for char in str: # str의 글자 하나하나를 점검한다.
hash_value = (hash_value * p + ord(char)) % m
return hash_value
def solution(string_list, query_list):
# ➋ string_list의 각 문자열에 대해 다항 해시값을 계산
hash_list = [polynomial_hash(str) for str in string_list]
# ➌ query_list의 각 문자열이 string_list에 있는지 확인
result = []
for query in query_list:
query_hash = polynomial_hash(query)
if query_hash in hash_list:
result.append(True)
else:
result.append(False)
return result
assert solution(['apple','banana','cherry'], ['banana','kiwi','melon','apple']) == [True,False,False,True], '출력값1 에러'
책의 기존 공식: (p**index * ord(char)) % m
그런데 해당 부분은 책의 설명과 달리 문자열에 해당하는 숫자값과 p가 곱셈관계가 아니고, p의 지수가 index가 아니라는 점에서 해시값을 지정하는 부분이 완전하지 못해보였다. 또한 초기값이 0이면 이에 곱해지는 p값도 문제가 생길 여지가 있어보인다. 그리고 해당 함수는 리스트에 대한 것이 아닌, 개별 문자열에 대한 해시값 반환 함수이므로 인덱스 지수승을 구현하긴 어려워보였다.
☞ 그렇지 않다. h 값의 갱신 과정을 생각해야한다.
h = ( (h*p + ord(char))%m) * p + ord(char)) % m여길 보면 h의 갱신과정이 p가 계속 곱해짐을 볼 수 있다. 여기서 지수가 생긴다. 이를 정리하면
h = ( ((h*p**2 + ord(char)*p)%m) + ord(char)) % m여길 보면 기존 식처럼 p의 지수는 h값이 갱신되면서 계속해서 늘어날 것이고, 이는 ord(char)와 곱셈관계에 있다.
이 식은 horner's rule이 적용된 개념이다.
이런 문자열 해싱 구현은 라빈카프 알고리즘과 연관된다.
# ➊ polynomial hash를 구현한 부분
def polynomial_hash(str): # 해시값 만드는 함수
p = 31 # 메르센 소수
m = 1_000_000_007 # 버킷 크기; 문제에 주어진 제약조건
hash_value = 1 # 값 할당
for char in str: # ord(): 문자값의 유니코드 반환
hash_value = (hash_value * p * ord(char)) % m
return hash_value
def solution(string_list, query_list):
# ➋ string_list의 각 문자열에 대해 다항 해시값을 계산
hash_list = [polynomial_hash(str) for str in string_list]
# ➌ query_list의 각 문자열이 string_list에 있는지 확인
result = [] # 정답지 통
for query in query_list:
query_hash = polynomial_hash(query)
# 대응되면 True, 아니면 False
result.append(query_hash in hash_list)
return result
assert solution(['apple','banana','cherry'], ['banana','kiwi','melon','apple']) == [True,False,False,True], '출력값1 에러'
책의 본문에 설명한 기본 문자열 해싱방법에 직관적으로 가깝게 적용해보았다. 빠진 것은 p의 지수값이 인덱스여야한다는 점 정도이다. 이렇게 했을 때에도 문제풀이에 지장은 없어보인다. 해시함수가 한 번 더 꼬인 느낌이 드는 정도이다.
해시함수 목적(같은값은 같은값, 다른값은 다른값 출력)에 부합한다면 문제되지 않는다.
문제 20) 완주하지 못한 선수
https://school.programmers.co.kr/learn/courses/30/lessons/42576
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
책의 풀이를 보면서 defaultdict 개념을 익힐겸 적용해보았다.
idea: 동명이인을 고려하기위해 dict로 이름을 받고, value는 각 이름의 개수로 한다. 개수를 차감시켜서 개수가 0이 아닌 key값을 출력한다.
# 1명빼고 모두 완주. 동명이인 有
# 목적: 그 1명이 누군지 출력
# 해시: dict로 key값 mapping
from collections import defaultdict
def solution(participant, completion):
dt = defaultdict(int) # value 없을때 기본값을 정함. int, set, list 사용可
for name in participant: # 이름(key) : 개수(value)
dt[name] += 1
for finisher in completion: # 완주자 value 개수 차감
dt[finisher] -= 1
for key, val in dt.items(): # value가 0이 아닌 것 출력
if val > 0:
return keydefaultdict의 용법(int, set, list)의 용도를 유념하자.
문제 21) 할인 행사
https://school.programmers.co.kr/learn/courses/30/lessons/131127
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
책의풀이를 보면서 하나하나 완성한 코드이다.
# 목적: want가 모두 할인可인 회원등록 날짜 총 일수
# numbers = want에 해당하는 수량. -> key = want : value = number 생각
# 제품은 하루에 하나씩만 구매 可 -> 가입기간이 10일 연속 일치해야함.
from collections import defaultdict
def solution(want, number, discount):
dt = defaultdict(int) # want : number
answer = 0
for key, val in zip(want, number): # 두 리스트 한번에 dict로 만들기
dt[key] = val
for i in range(len(discount) - 9): # 10개씩 이동하는 형태
temp = defaultdict(int) # 임시 기준 dict(반드시 여기서 초기화)
for j in range(i, i + 10):
if discount[j] in dt: #자동+1 개수세기
temp[discount[j]] += 1
if dt == temp:
answer += 1
return answer10개씩 이동하는 range 범위 설정법에 유의한다. (len(dicount) - 9)와 이중 for문의 range(i, i+10)
그리고 temp의 초기화 위치, zip 함수의 활용
그런데 중간에 defaultdict을 사용한다는 점에서 불필요한 if연산을 줄일 수 있다.
from collections import defaultdict
def solution(want, number, discount):
dt = defaultdict(int) # want : number
answer = 0
for key, val in zip(want, number):
dt[key] = val
for i in range(len(discount) - 9):
temp = defaultdict(int)
for j in range(i, i + 10):
# if discount[j] in dt: 생략 可
temp[discount[j]] += 1
if dt == temp: # 어차피 검증은 여기서 한다.
answer += 1
return answer해당 부분이 생략가능한 이유는 temp도 defaultdict이므로 없는 값에 대해서 오류를 발생시키지않고, 자동으로 default값을 추가하기 때문이다. 검증하는 부분은 if dt == temp: 에서 진행되므로, 해당 부분에서 검증이 완전하지 않더라도 전체 문제풀이에 지장을 주지 않는다.
if 연산이 하나 줄어드니 전보다 속도가 더 빨라졌다.
다른 사람의 풀이
from collections import Counter
def solution(want, number, discount):
answer = 0
dic = {}
for i in range(len(want)):
dic[want[i]] = number[i]
for i in range(len(discount)-9):
if dic == Counter(discount[i:i+10]):
answer += 1
return answerCounter 함수를 이용해서 푸는게 더 간단할지도 모르겠다. 이게 더 빠름..
문제 22) 오픈 채팅방 (카카오2019)
https://school.programmers.co.kr/learn/courses/30/lessons/42888
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
# 닉네임 변경 법: 나갔다가 새 닉네임으로 들어오기 or 채팅방 내 닉네임 변경
# 닉네임 변경 효과: 기존 출력된 메세지의 닉네임도 전부 변경
# 중복 닉네임을 허용한다. '유저id'로 구분한다.
# record: 채팅방 출입기록, 닉 변경 기록. 나간 유저가 닉변경하는 경우는 없음
# record 구조: "Enter or Leave or Change // uid#### // 닉네임"
# 목적: record 전부 처리한 후 나올 최종 출력물?
# dict를 갱신하는 uid : nick 구조로 dict 만듦 - > 최종 id와 nick 정리한 dict
from collections import defaultdict
def solution(record):
dt = defaultdict(str) # id : 최종 nick 정리 통
answer = [] # 정답 메세지 통
for i in record:
cmd, uid, *nick = i.split() # 항상 3개가 아님. leave는 nick이 없으므로 *를 붙임
# id를 key로 받고 nick(value)를 갱신 -> change, 나갔다들어오기 순서 자동 포함
if nick: # 제일 중요한 부분! nick이 없는 경우의 갱신이 이상해지거나 런타임 에러!!
dt[uid] = nick # *nick는 나머지처리이므로 list로 value값이 저장됨
for i in record:
cmd, uid, *nick = i.split()
if cmd == 'Enter': # dt의 value가 list로 저장되었으므로 [0]을 붙인다.
answer.append(f"{dt[uid][0]}님이 들어왔습니다.")
elif cmd == 'Leave':
answer.append(f"{dt[uid][0]}님이 나갔습니다.")
return answerdict 형성의 요점은 {uid : nick}으로 record를 전부 순회하여 최종 갱신하는 것이다. (혼자서 생각하지 못했다.)
주의할 점은 leave 명령어는 문자열이 2개뿐이므로 nick이 없다. 이것과 관련된게 if nick: 부분이다.
if nick이라는 조건은 매우 중요하다. 이것이 없으면 1번과 16번만 통과하고 전부 오류가 뜨거나 런타임 에러가 난다.
i.split()에서 값을 할당할 때, 있거나 없거나한 경우에 *을 붙여서 나머지 처리를 할 수 있다.
이렇게 처리된 값의 경우, 그 길이가 가변적이라고 상정하기때문에 리스트로 value값이 저장된다.
그러므로 마지막 메세지 출력에서 dt[uid]가 아니라 dt[uid][0]을 시행한 것이다.
원래는 dt[i.split()[0]] = i.split()[-1] 로 dt를 만들었는데 좀 더 이쁘고 효율적(?)으로 정리한 코드이다.
문제 23) 베스트 앨범 (level 3)
https://school.programmers.co.kr/learn/courses/30/lessons/42579
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
망한 풀이
# 장르 > 최다재생 > 낮은 고유번호(=파이썬 인덱스). 같은 장르는 최대 2개까지만 수록 可
# 목표: 이 기준으로 들어갈 노래의 고유번호 순서
# 다른 두 장르가 동일 재생횟수인 경우 X (같은 장르내에서는 동일 횟수 可)
# 구조: {인덱스 : genres} -> plays 맵핑. plays를 list로 받아야 함
# 인덱스는 plays에서 가져오자.
from collections import defaultdict
def solution(genres, plays):
answer = [] # 정답통
dt1 = defaultdict(list) # {장르 : [각 횟수]}
for g, p in zip(genres, plays):
dt1[g].append(p)
# value값이 큰 순서대로 key값 내림차순 정렬
dt1 = dict( sorted(dt1.items(), key=lambda x: sum(x[1]), reverse=True) )
# 각 value값을 큰 순서대로 내림차순 정렬 + 큰값 2개만 뽑기
dt1 = {genre: sorted(values, reverse=True)[:2] for genre, values in dt1.items()}
for key, val in dt1.items():
for v in val:
answer.append(plays.index(v))
return answer이렇게 하면 2번과 15번이 통과하지 않는다. 마지막에 고유값을 기준으로 추가하는 개념이 누락되었기 때문이다.
갈아엎어야되는 상황이다.
이럴 때는 결국 GPT가 정답을 갈아엎으면서 가이드를 제시했다.
from collections import defaultdict
def solution(genres, plays):
answer = [] # 정답 통
dt1 = defaultdict(list) # {장르 : [재생 횟수]}
for i, (genre, play) in enumerate(zip(genres, plays)):
dt1[genre].append((play, i)) # (재생 횟수, 고유번호)를 리스트에 저장
# value값이 큰 순서대로 key값 내림차순 정렬
dt1 = dict(sorted(dt1.items(), key=lambda x: sum(p for p, _ in x[1]), reverse=True))
# 각 value값을 큰 순서대로 내림차순 정렬
dt1 = {genre: sorted(values, key=lambda x: -x[0])[:2] for genre, values in dt1.items()}
# 정답에 추가 (고유번호 뽑기)
for values in dt1.values():
answer.extend([index for _, index in values])
return answerdict 컴프리핸션에 쓰인 lambda의 정렬 표현과 for문 연결, extend.. 낯선 코드 투성이.
문제 24) 신고 결과 받기 (카카오 2022)
https://school.programmers.co.kr/learn/courses/30/lessons/92334
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
책을 안보고 차근차근 문제를 쪼개서 푼 것
# 신고 횟수 제한 X: 단, 한 번당 한 명 유저 신고.
# 중복 신고 可: 단, 중복 신고는 1회처리
# k번 이상 신고된 유저 -> 정지 & 이 유저를 신고한 모든 유저에게 이 사실 알림
# id_list: 전체 유저 // report: 누가 누굴 신고했는지 // k = 정지 기준
# 목표: id_list 각 유저들이 메일을 받은 횟수 출력
# 출력을 위한 필요정보: 각 유저가 신고한 ID, 각 유저별 신고당한 횟수
# dt1 = {유저id : 신고한 id} -> 여기서 dt2 = {유저id : 신고당한 횟수} 도출(dt1로 중복신고 처리)
# dt2에서 정지된id 리스트 lst 도출 -> dt1 value가 lst에 있는 횟수 출력(목표)
from collections import defaultdict
def solution(id_list, report, k):
# dt1 = {유저id : [신고한 id 리스트]} + 정렬기준은 id_list
dt1 = defaultdict(list)
for key in id_list: # id_list정렬 기준으로 key값 통 생성
dt1[key] = []
for i in report: # value값 반영
dt1[i.split()[0]].append(i.split()[1])
# dt1을 set으로 value값 중복 제거
for key, val in dt1.items():
dt1[key] = list(set(val))
# dt2 = {유저id : 신고당한 횟수} 도출
dt2 = defaultdict(int)
for val in dt1.values():
for i in range(len(val)):
dt2[val[i]] += 1
# dt2에서 정지된id 리스트 lst 도출
lst = [key for key in dt2 if dt2[key] >= k]
# dt1 value와 lst를 비교하여 answer 갱신
answer = [0] * len(id_list) # 기본값은 0
for i, key in enumerate(id_list):
for reported_id in dt1[key]: # dt1[key] = 신고id 리스트
if reported_id in lst: # lst에 있으면 값 +1
answer[i] += 1
return answer마지막 answer갱신과정이 비효율적이다.
차근차근 풀어서 통과하긴 했는데 테스트3처럼 시간이 걸리는 경우가 좀 있다. O(N^2)방식이고 dict 구성이 비효율적(?)이여서 코드가 길어졌다. 구현시간도 자잘한 문법오류로 1시간 조금 넘은듯 하다.
숏코딩 아이디어
def solution(id_list, report, k):
answer = [0] * len(id_list) # 정답통 (default = 0)
reports = {x : 0 for x in id_list} # {기존 id : 신고당한 횟수}
for i in set(report): # 중복방지 set
reports[i.split()[1]] += 1
for i in set(report):
if reports[i.split()[1]] >= k: # key가 정지된 이용자이면
answer[id_list.index(i.split()[0])] += 1
# 신고한 유저가 있는 id_list의 index위치에 +=1 (메일 개수)
return answer어려웠던 부분:
딕셔너리 컴프리헨션으로 key값 자동 정렬 아이디어
그냥 report가아닌 set(report)를 순회하는 아이디어
메일 개수 = id_list.index(신고한 유저) 라는 아이디어 -> 문제는 index()연산때문에 시간에 걸릴 수 있다는 단점 有
저자의 풀이
def solution(id_list, report, k):
reported_user = { } # 신고당한 유저 - 신고 유저 집합을 저장할 딕셔너리
count = { } # 처리 결과 메일을 받은 유저 - 받은 횟수를 저장할 딕셔너리
# ➊ 신고 기록 순회
for r in report:
user_id, reported_id = r.split( )
if reported_id not in reported_user: # ➋ 신고당한 기록이 없다면
reported_user[reported_id] = set( )
reported_user[reported_id].add(user_id) # ➌ 신고한 사람의 아이디를 집합에 담아 딕셔너리에 연결
for reported_id, user_id_lst in reported_user.items( ) :
if len(user_id_lst) >= k: # ➍ 정지 기준에 만족하는지 확인
for uid in user_id_lst: # ➎ 딕셔너리를 순회하며 count 계산
if uid not in count:
count[uid] = 1
else:
count[uid] += 1
answer = [ ]
for i in range(len(id_list)): # ➏ 각 아이디별 메일을 받은 횟수를 순서대로 정리
if id_list[i] not in count:
answer.append(0)
else:
answer.append(count[id_list[i]])
return answer
여기서는 idea: dict 구조를 {신고당한유저 : 신고유저 집합}으로 두었고, 신고메일 받는 count dict을 만들었다.
defaultdict로 변형해본 저자의 답안이다.
from collections import defaultdict
def solution(id_list, report, k):
dt = defaultdict(set) # dt = {신고당한유저 : 신고유저 집합}
mail_count = defaultdict(int) # mail_count = {신고한 유저: 메일받은 횟수}
for i in report: # {신고당한유저 : 신고유저 집합}
val, key = i.split() # val(신고한 유저)과 key(신고당한유저)의 순서에 주목한다.
dt[key].add(val)
# for key, val in dt.items(): dt 생김새를 보려면 이 코드가 필요하다.(없으면 JSON오류)
# dt[key] = list(set(val))
for who_reported in dt.values(): # 신고한 유저들 집합에 대해서
if len(who_reported) >= k: # 이용정지 조건에 해당되는 유저가 key라면,
for uid in who_reported: # 그 유저들 신고한 사람들에게
mail_count[uid] += 1 # 메일이 전송된다.
answer = []
for i in range(len(id_list)): # id_list로 순회해서 자동 정렬
if id_list[i] not in mail_count: # 메일받은 유저가 아니면
answer.append(0) # 0으로 입력
else:
answer.append(mail_count[id_list[i]])
return answer어려웠던 부분:
dict = {신고당한 유저 : 신고유저 집합}으로 거꾸로 구현해야한다는 아이디어 떠올리기
mail_count = {신고한 유저: 메일받은 횟수} 라는 메일 받은 횟수를 구현하는 아이디어 떠올리기
속도가 이전에 비해서 좋아졌다.
문제 25) 메뉴 리뉴얼 (카카오 2021)
https://school.programmers.co.kr/learn/courses/30/lessons/72411
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
스스로 풀려다가 문제가 난잡해져서 저자의 풀이로 대체하기로 했다.
from itertools import combinations
from collections import Counter
def solution(orders, course):
answer = []
for c in course: # ➊ 각 코스 요리 길이에 대해
menu = []
for order in orders: # 모든 주문에 대해
comb = combinations(sorted(order), c) # ➋ 조합(combination)을 이용해 가능한 메뉴 구성을 모두 구함
menu += comb
counter = Counter(menu) # ➌ 각 메뉴 구성이 몇 번 주문되었는지 세어줌
if len(counter) != 0 and max(counter.values()) != 1: # ➍ 가장 많이 주문된 구성이 1번 이상 주문된 경우
for m, cnt in counter.items() :
if cnt == max(counter.values()): # ➎ 가장 많이 주문된 구성을 찾아서
answer.append("".join(m)) # ➏ 정답 리스트에 추가
return sorted(answer) # ➐ 오름차순 정렬 후 반환
most_common(): 가장 높은 빈도부터 내림차순 정렬하는 것 을 활용한 타인의 코드
from collections import Counter
from itertools import combinations
def solution(orders, course):
result = []
for course_size in course:
order_combinations = []
for order in orders:
order_combinations += combinations(sorted(order), course_size)
# most_common(): 최빈값기준 내림차순 정렬
# most_ordered = {메뉴알파벳 : 등장횟수}
most_ordered = Counter(order_combinations).most_common()
# k: 메뉴 // v: 해당 메뉴 개수 // 2번이상 등장한 v에서 최빈값인 것
# result에 메뉴 알파벳 계속 추가(course_size 변화 갯수만큼)
result += [ k for k, v in most_ordered if v > 1 and v == most_ordered[0][1] ]
# result 오름차순 정렬한 것을 붙여서 리스트로 정리
return [ ''.join(v) for v in sorted(result) ]
추천 문제 1) 의상
https://school.programmers.co.kr/learn/courses/30/lessons/42578
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드 작성이 문제가 아니라 수학적 역량(경우의수, 조합)을 따지는 문제였던 것 같다.
# 매일 다른 옷 조합해서 입기. 종류별 1개만 착용 可. 일부가 겹쳐도 추가되면 다른방법으로 인정
# clothes: 옷 리스트 목표: 서로 다른 옷 조합의 수
# dt = {옷의 종류: 옷 리스트}
# 수학적 아이디어 : 안입는 경우가 각 품목별로 'nude' 가 있다고 가정해야 한다.
# 각 종류별로 1개까지만 착용이 가능하므로 전체길이C1을 종류만큼 곱하는 것이다.
from collections import defaultdict
def solution(clothes):
dt = defaultdict(list)
for i in clothes:
dt[i[1]].append(i[0])
answer = 1 # 0을 곱하면 안되므로 1로 초기화
for val in dt.values():
answer *= len(val) + 1 # 여기서 더해지는 1은 각 카테고리별 nude인 경우 추가하는 것.
return answer - 1 # 모두 안입는 nude경우 제외수학 공식으로 경우의 수 찾는 것을 도출했으니 시간복잡도도 O(N)에서 그쳤다.
추천 문제 2) 압축 (카카오 2018)
https://school.programmers.co.kr/learn/courses/30/lessons/17684
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
# ord('A') = 65 -> ord()값에 -64 를 반영
# 새 글자는 27부터 반영되어 1씩 증가하며 추가
def solution(msg):
dt = {chr(i) : i - 64 for i in range(65, 91)} # {전체 알파벳 : 1~26 숫자} 선입력
answer = []
w = msg[0] # w = 현재 글자
for c in msg[1:]: # c = 다음 글자
wc = w + c # (w+c) 라는 글자 정의
if wc in dt: # 만약 (w+c)가 이미 있는거라면
w = wc # (w+c) + c 구조로 확장
else: # (w+c)라는 글자가 없다면
answer.append(dt[w]) # 현재 문자열 값 업데이트 (유일 업데이트 코드)
dt[wc] = len(dt) + 1 # (w+c) 값 업데이트
w = c # w 재정의
answer.append(dt[w]) # 마지막 남은 값 업데이트
return answerLZW(Lempel-Ziv-Welch) 압축 알고리즘을 구현하는 문제인데 설명으로 이런 구조를 구현하기 어려워보인다.
'TechStudy > CodingTest' 카테고리의 다른 글
| chp10 집합(set) (0) | 2024.01.06 |
|---|---|
| chp9 트리(tree) (4) | 2023.12.21 |
| chp6 스택(Stack), chp7 큐(Queue) (4) | 2023.12.07 |
| 백준 1차원 배열 10문제, 2차원 배열 단계 4문제 풀이 (1) | 2023.11.30 |
| chp5 배열(Array) (1) | 2023.11.28 |
