대충 글을 읽어보니
내가 공부했던 정수론과 암호론이랑 Hash는 깊은 연관관계가 있는 자료 구조형으로 보임
특히, 해시함수가
나중에 더 깊이 공부할 필요가 생기면 따로 정리해 둘 것
문제 18. 두 개의 수로 특정값 만들기
내가 한 것 :
## question 18
def solution(arr, target):
map = dict()
for member in arr:
map[member] = target - member
for key, value in map.items():
try:
answer = map[value]
print('answer is ', answer)
if key == value:
continue
else:
return 'True'
except:
continue
return 'False'
arr = [1, 2, 3, 4, 8]
target = 6
print(solution(arr, target))
arr = [2, 3, 5, 9]
target = 10
print(solution(arr, target))arr의 길이를 N, target의 크기를 K라고 할 때
내가 한 풀이의 시간복잡도는 O(N+N) 같은데..
(답지는 O(N+K)를 말하는데 내꺼가 더 낫지 않나? 우하하)
💡GPT의 조언
1) 나는 try-except구문을 잘 사용하는 편인데 이게 일단 추천하지 않음
: try-except구문에서 예외 상황이 발생하면, 내부적으로 stack-frame을 발생하고 예외객체를 생성하는 등 예외처리를 위한 다른 일을 진행함! 몰랐어!!
그렇기 때문에 진짜 예외처리를 위해서 사용하는 것이 좋음
2) map은 실제 python에 있는 내장함수이기 때문에 사용하는걸 추천하지 않음
: map은 python에서 iterable 객체에 함수를 취해주는 내장함수
list(map(round, [1.1, 2, 3.5]))이런식으로..
※ (참고) map은 그럼 시간복잡도가 몇일까?
일단 map을 한다고 해서 다 계산하지 않음
그냥 next로 호출되면 계산될 뿐.
그래서 한번은O(1)인데 이걸 전체의 list안에 있는 만큼 반복하면O(N)이 됨
3) 그리고 미안하지만 네가 한 것에서 시간복잡도는 O(N)~O(N^2)란다
: 책에서 나온 것처럼 hash 함수에서 충돌이 생긴다면,
내가 제안한 map[value]는 시간복잡도가 O(1)이 아니라 최악의 경우(모든 key-value가 충돌하는 경우) O(N)이 될 수 있음
이 구문이 지금 for문 안에 있으니까 O(N^2)가 될 수 있음....(조금 억지같지만 맞말..)
그럼 gpt의 조언에 따라 코드를 바꾸면
## question 18
def solution(arr, target):
arr_target = dict()
for member in arr:
arr_target[member] = target - member
for key, value in arr_target.items():
if (key != value) and value in arr_target:
return 'True'
return 'False'
arr = [1, 2, 3, 4, 8]
target = 6
print(solution(arr, target))
arr = [2, 3, 5, 9]
target = 10
print(solution(arr, target))책에서 제안한 것 :
def count_sort(arr, k):
## hash table의 생성 및 초기화 ---!!!
hashtable = [0] * (k+1)
for num in arr:
if num <= k:
hashtable[num] = 1
return hashtable
def solution(arr, target):
hashtable = count_sort(arr, target)
for num in arr:
complement = target - num
if (
complement != num
and complement >= 0
and complement <= target
and hashtable[complement] == 1
):
return True
return False차이를 보면 일단 이건 hashtable을 직접 생성함 - 충돌이 있을 수가 없긴해;;
근데 충돌이 안생기면 처음 초기화 하면서 시간복잡도가 O(K)이고 for문 한번 돌면서 O(N)이고
solution에서의 for문 한번 더 돌면서 O(N)이니까 나보다 더 시간복잡도가 높을 수도 있을 것 같은데?
근데 time으로 테스트해보니까 큰 수로 했을 때, 내 코드(dictionary-based code)가 array-based code보다 느렸음.
gpt가 분석했을 때, 이는 메모리 재할당 때문인것으로 추측됨.
나는 arr를 돌면서 하나하나 key-value로 dictionary에 추가하는데 arr가 과도하게 크면 처음 할당된 메모리가 다 차버려서 새롭게 메모리를 재할당 해주는 일이 발생함.
그럴 경우에, 전체 데이터를 다른 메모리로 옮기기 때문에 O(N)의 복잡도가 발생하게됨
때문에 처음부터 메모리 크기를 K에 맞게 크게 할당한다? = array-based code가 됨
정리하면 k값이 큰데 arr가 적은 경우에 array-based code는 굉장히 비효율적일 수 있지만, arr도 그만큼 큰 경우 dictionary-based는 메모리 재할당이 발생할 수 있어서
오히려 비효율적일 수 있다는 얘기!!
문제 19. 문자열 해싱을 이용한 검색 함수 만들기
여기서 hash table을 직접 만드는데,
내가 할 엄두가 안나서 책을 그대로 따라함
## question 19
# string_list의 길이 N
# query_list의 길이 K
# string 한 개의 길이 M
def polynomial_hash(str):
p = 31
m = 1_000_000_007
hash_value = 0
for chr in str: # -- O(M)
hash_value = (hash_value * p + ord(chr)) % m
return hash_value
def solution(string_list, query_list):
hash_list = [polynomial_hash(str) for str in string_list] # -- O(M*N)
answer_list = []
for query in query_list: # -- O(K)
query_hash = polynomial_hash(query) # -- O(M)
if query_hash in hash_list: # -- O(N)
answer_list.append(True)
else:
answer_list.append(False)
return answer_list
string_list = ['apple', 'banana', 'cherry']
query_list = ['banana', 'kiwi', 'melon', 'apple']
print(solution(string_list, query_list))근데 의문인 점은 내가 생각하기에 이 문제의 시간복잡도는
O(K*(N+M)+M*N)인데 이 책에서는 O(K+N)으로 해석한다는 점..??
이 부분 이해가 안 감
그래서 내가 다시 해봄
내가 한 것 :
def solution_yb(string_list, query_list):
string_dict = dict()
answer_list = []
for string in string_list:
string_dict[string] = 1
for query in query_list:
if query in string_dict:
answer_list.append(True)
else:
answer_list.append(False)
return answer_list이렇게 해서 시간 계산했을 때
solution_book이 훨씬 느린걸 보아..
아무래도 list로 hash를 만든것 자체가 잘못되지 않았나
조심스럽게 문제제기를 해봅니다
문제 20. 완주하지 못한 선수
내가 한 것 :
## question 20
def solution(participant, completion):
completion_dict = set(completion) ## - O(N)
remain = []
for p in participant:
if p in completion_dict:
continue
else:
remain.append(p)
return remain
participant = ['leo', 'kiki', 'eden']
completion = ['eden', 'kiki']
print(solution(participant, completion))내 의견 : dict도 그렇고 set도 그렇고 결국 hash 방식으로 데이터를 다루니까
특히 결국 hash table의 크기를 제한해서 초기화해서 메모리를 적절히 할당할 수 있는게 아니라면 직접 hash-table을 구현하는 것보다는 dict와 set를 사용하는게 적절하다고 생각함.
특히 지금처럼 유무만을 따지는 경우 dict를 사용하여 불필요한 value를 지정할 필요 없이 set으로 포함관계만 사용하면 되니까 더 적절하지 않나?
아, 근데 이 경우에 지금 동명이인이 있기 때문에 value 지정이 필요함;;
dict로 해야할 듯
내가 수정한 것 :
## question 20
## question 20
def solution(participant, completion):
completion_dict = {}
for c in completion:
if c in completion_dict:
completion_dict[c] += 1
else:
completion_dict[c] = 1
for p in participant:
if p in completion_dict:
completion_dict[p] -= 1
else:
return p
for key, value in completion_dict.items():
if value == -1:
return key
# participant = ['leo', 'kiki', 'eden']
# completion = ['eden', 'kiki']
participant = ['mislav', 'stanko', 'mislav', 'ana']
completion = ['stanko', 'ana', 'mislav']
print(solution(participant, completion))근데 예전의 내가 한걸 찾았는데 조금 더 똘똘함
from collections import Counter
def solution(participant, completion):
participant = Counter(participant)
for finisher in completion:
participant[finisher] -= 1
if participant[finisher] == 0:
del participant[finisher]
return ''.join([str(key) for key in participant.keys()])
participant = ['mislav', 'stanko','mislav', 'ana']
completion = ['stanko', 'ana', 'mislav']
print(solution(participant, completion))일단 Counter를 사용해서 처음 O(N)짜리를 한줄로 표현하고
조건을 충족시키면 dictionary값을 0을 만드는걸 떠나서 걍 지워버림ㅋㅋㅋ
그래서 마지막 O(N)을 없앰
더 시간복잡도가 개선될 듯?
근데 programmers에서는 효율성과 정확도가 동일함;;
상수계수 차이는 정말 성능측면에서 미미하다고 합니다..
물론 N이 엄청크면 조금 다르기야 하지만 그래도 아주 미미하다고 하네요;;
오히려 가독성 측면에서 programmers의 다른 답변 중에 가장 좋았던 답변은
import collections
def solution(participant, completion):
answer = collections.Counter(participant) - collections.Counter(completion)
return list(answer.keys())[0]여기서 내가 몰랐던 것 : collections.Counter는 뺄셈이 가능하다!!
문제 21. 할인 행사
내가 한 것:
## question 21
from collections import Counter
def solution(want, number, discount):
shop_list = {}
for i in range(len(want)): # -- O(M)
shop_list[want[i]] = number[i]
buy_days = 0
for j in range(len(discount)): # -- O(N)
scope = Counter(discount[j:j+10]) # -- O(10)
for product in want: # -- O(M)
if (product in scope and scope[product] >= shop_list[product]):
try_next_day = False
continue
else:
try_next_day = True
break
if try_next_day:
continue
else:
buy_days += 1
return buy_days
want = ['banana', 'apple', 'rice', 'pork', 'pot']
number = [3, 2, 2, 2, 1]
discount = ['chicken', 'apple', 'apple', 'banana', 'rice', 'apple', 'pork', 'banana', 'pork', 'rice', 'pot', 'banana', 'apple', 'banana']
print(solution(want, number, discount))답변을 보면 dict(scope) == shop_list로 표현했는데
이게 더 직관적이긴 하지만 제한이 좀 필요함
근데 문제에 그 제한이 다 적혀있음;;
또 무엇보다 내가 몰랐던 것💡
dictionary에서 없는 key값을 조회하려고 할 때, key-except를 썼었는데
여기서 유용한 method가 바로geta = {'yb':31, 'sb':32} #방법 1 a['yb'] # 31 a['jm'] # Key error #방법 2 a.get('yb') # 31 a.get('jm') # None a.get('jm', 0) # 0
문제 22. 오픈 채팅방
내가 한 것:
## question 22
def solution(record):
user = {}
result = []
for log in record:
log = log.split()
if log[0] in ['Enter', 'Change']:
user[log[1]] = log[2]
# print(user)
for log in record:
log = log.split()
if log[0] == 'Enter':
msg = f"{user[log[1]]}님이 들어왔습니다."
result.append(msg)
elif log[0] == 'Leave':
msg = f"{user[log[1]]}님이 나갔습니다."
result.append(msg)
return result
record = ["Enter uid1234 Muzi", "Enter uid4567 Prodo", "Leave uid1234", "Enter uid1234 Prodo", "Change uid4567 Ryan"]
result = ["Prodo님이 들어왔습니다.", "Ryan님이 들어왔습니다.", "Prodo님이 나갔습니다.", "Prodo님이 들어왔습니다."]
print(solution(record))굿!
문제 23. 베스트 앨범
내가 한 것 :
## question 23
def solution(genres, plays):
# 가장 인기있는 장르 sorting + 장르별 노래 sorting
genres_sum = {}
musics = {}
for i in range(len(genres)):
genres_sum[genres[i]] = genres_sum.get(genres[i], 0) + plays[i]
if genres[i] in musics:
musics[genres[i]][i] = plays[i]
else:
musics[genres[i]] = {i:plays[i]}
genres_order = sorted(genres_sum, reverse=True, key= lambda x : genres_sum[x])
# print(musics)
# 가장 인기있는 장르 순으로 노래 선곡
album_list = []
for genre in genres_order:
# print(sorted(musics[genre], reverse=True, key = lambda x : musics[genre][x]))
album_list += sorted(musics[genre], reverse=True, key = lambda x : musics[genre][x])[:2]
return album_list
genres = ["classic", "pop", "classic", "classic", "pop"]
plays = [500, 600, 150, 800, 2500]
result = [4, 1, 3, 0]
print(solution(genres, plays))내가 잘 몰랐던 것 :
sorted vs. sort
sorted: python 내장함수. 주어진 argument(iterable object)를 정렬한 후에 새로운 list 형태로 반환한다
sort: list의 method. list를 정렬해서 변환시킨다. 원본 리스트를 바꾸기 때문에(in-place) 반환값 자체는 None이다
sorted
sorted는 iterable object를 인자로 받고 key를 기준으로 정렬하는데,
key에는 함수가 들어간다예를 들면
a = ['banana', 'apple', 'kiwi'] sorted(a, key = len) # ['kiwi', 'apple', 'banana']또다른 예를 들어보자면
a = {'banana':3, 'apple':4, 'kiwi':5} sorted(a, key = lambda x:a[x]) # ['banana', 'apple', 'kiwi']또는,
a = {'banana':3, 'apple':4, 'kiwi':5} sorted(a.items(), key = lambda x:x[1])
문제 24. 신고 결과 받기
내가 한 것 :
## question 24
def solution(id_list, report, k):
result = []
# user들의 complain list 초기화
complained_list = {}
complain_list = {}
for id in id_list: # -- O(M)
complained_list[id] = set()
complain_list[id] = set()
# report 분류
for complain in report: # -- O(N)
complain = complain.split()
complained_list[complain[1]].add(complain[0])
complain_list[complain[0]].add(complain[1])
# 신고 당한 갯수 count
for user in id_list: # -- O(M)
mailing = 0
for bad_user in complain_list[user]: # -- 최대 O(M) : 자기 빼고 전부 신고
if len(complained_list[bad_user]) >= k:
mailing += 1
result.append(mailing)
return result
id_list = ["muzi", "frodo", "apeach", "neo"]
report = ["muzi frodo","apeach frodo","frodo neo","muzi neo","apeach muzi"]
k = 2
result = [2, 1, 1, 0]
print(solution(id_list, report, k))report의 길이를 N, id_list의 길이를 M이라고 했을 때
내가 짠 코드는 사실 O(N+M)~O(N+M+M^2)라고 할 수 있음
문제에서 N < 2e+5, M < 1e+3 이라고 제시했기 때문에
한놈이 찌를 수 있는 다른 사람의 수가 제한되긴함
그래도 좀 아쉬움..
다른 사람의 문제 풀이 중에 조금 신박한게 있다면
report 자체에 set을 취한 방법이 조금 새로움
근데 풀이 속도는 비슷해보임
def solution(id_list, report, k):
answer = [0] * len(id_list)
complained = {x:0 for x in id_list}
reports = set(report)
for r in reports:
complained[r.split()[1]] += 1
for r in reports:
if complained[r.split()[1]] >= k:
answer[id_list.index(r.split()[0])] += 1
return answer문제 25. 메뉴 리뉴얼
내가 한 것:
def solution(orders, course):
orders_set = order_to_set(orders)
intersect_dict = intersect(orders_set)
intersect_dict_correct = intersect_dict.copy()
answer = []
for course_num in course:
for menu_combi, order_count in intersect_dict.items():
if len(menu_combi) > course_num:
new_menu_combis = combination(menu_combi, course_num)
for new_menu_combi in new_menu_combis:
if new_menu_combi in intersect_dict:
intersect_dict_correct[new_menu_combi] += order_count
else:
intersect_dict_correct[new_menu_combi] = order_count
# print(intersect_dict_correct)
for course_num in course:
max_order = 0
choose_menu = []
for menu_combi, order_count in intersect_dict_correct.items():
if len(menu_combi) == course_num:
if order_count > max_order:
max_order = order_count
choose_menu = [menu_combi]
elif max_order == order_count:
choose_menu.append(menu_combi)
answer += choose_menu
answer = set(answer)
return sorted(answer)
def combination(menu_combi, course_num, start = 0, current = None, result = None):
if current == None:
current = []
if result == None:
result = []
if len(current) == course_num:
result.append("".join(current))
# print(result)
return result
for i in range(start, len(menu_combi)):
combination(menu_combi, course_num, i+1, current + [menu_combi[i]], result)
return result
def intersect(orders_set):
intersect_dict = {}
while orders_set:
current_check = orders_set.pop()
for order_set in orders_set:
find_intersect = current_check.intersection(order_set)
if len(find_intersect) > 1:
menu_combination = str()
for menu in sorted(find_intersect):
menu_combination += menu
if menu_combination in intersect_dict:
intersect_dict[menu_combination] += 1
else:
intersect_dict[menu_combination] = 1
return intersect_dict
def order_to_set(orders):
orders_set = []
for order in orders:
order_set = set()
for menu in order:
order_set.add(menu)
orders_set.append(order_set)
return orders_set테스트케이스에서 우르르쾅쾅인데 시간을 너무 오래 쏟을 수 없어서 여기까지..
