자료구조 2주차 복습&숙제
요세푸스 문제
📄 나의 코드 (데크 사용 deque)
# BOJ 1158
from collections import deque
def josephus_problem(n, k):
deq = deque()
for i in range(n):
deq.append(i + 1)
result = '<'
cnt = 0
while len(deq) != 0:
if cnt == k-1:
cnt = -1
if len(deq) == 1:
result += str(deq[0]) + '>'
else:
result += str(deq[0]) + ', '
deq.popleft()
else:
temp = deq.popleft()
deq.append(temp)
cnt += 1
return print(result)
n, k = map(int, input().split())
josephus_problem(n, k)
저번에 list로 제출한 것과 로직 동일!
동일한 로직이지만, 자료구조를 뭘 사용하냐에 따라 시간초과가 날 수 도 있고 '맞습니다!!' 결과가 나올 수도 있다.
리스트로 풀어보는 방법은 답안 코드를 보고 학습해 보았다.
📄 답안코드
# BOJ 1158
def josephus_problem(n, k):
result_arr = []
next_index = k - 1
people_arr = list(range(1, n + 1))
while people_arr:
result = people_arr.pop(next_index)
result_arr.append(result)
if len(people_arr) != 0:
next_index = (next_index + (k - 1)) % len(people_arr)
print("<", ", ".join(map(str, result_arr)), ">", sep='')
n, k = map(int, input().split())
josephus_problem(n, k)
next_index를 (k번째 요소 인덱스는 (k-1)니깐)를 k-1씩 증가시고 index 초과할 수 있으니 이를 list의 길이만큼 나눈 나머지값을 next_index로 사용한다.
수학적인 수식으로 문제를 접근하면 list을 활용해서 풀수 있구나!
📌 리스트 range 활용해 할당
>>> a = list(range(10))
>>> a
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
아래는 문제에서 원하는 출력 형식을 맞춰주기 위해 활용한 문법들이다.
📌 join, map
",".join(map(str, result_arr))
[3, 6, 2, 7, 5, 1, 4] → 3,6,2,7,5,1,4
", ".join(map(str, result_arr))
[3, 6, 2, 7, 5, 1, 4] → 3, 6, 2, 7, 5, 1, 4
📌 sep
print('S','E','P', sep='@')
>>>>> S@E@P
@활용해 SEP를 구분!
"<", ", ".join(map(str, result_arr)), ">", sep=''
< 3, 6, 2, 7, 5, 1, 4 > → <3, 6, 2, 7, 5, 1, 4>
숙제1. 링크드 리스트 끝에서 k번째 값 출력하기
📄 나의 코드
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def get_kth_node_from_last(self, k):
cur = self.head
cnt = 0
while cur.next is not None:
cur = cur.next
cnt += 1
node = self.head
count = 0
while count <= cnt - k:
node = node.next
count += 1
return node
linked_list = LinkedList(6)
linked_list.append(7)
linked_list.append(8)
print(linked_list.get_kth_node_from_last(2).data) # 7이 나와야 합니다!
cnt는 리스트 끝 index값이 되도로 하고
count는 끝에서 k번째 index값이 되도록 코드를 짠다.
📄 답안코드
def get_kth_node_from_last(self, k):
slow = self.head
fast = self.head
for i in range(k):
fast = fast.next
while fast is not None:
slow = slow.next
fast = fast.next
return slow
첫번째 답안 코드는 나와 로직이 같아 생략.
두번째 답안코드는 신기했다.
slow는 끝에서 k번째 떨어진 위치까지 next~
fast는 끝까지 next하는 방식으로 이동!
slow을 반환하면 끝에서 k번째 노드에 위치하는 노드가 반환된다.
숙제2. 배달의 민족 배달 가능 여부
📄 나의 코드
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["만두", "콜라", "만두"]
def is_available_to_order(menus, orders):
# 이 부분을 채워보세요!
# 문자열 sort 필수!
menus.sort()
results = []
for order in orders:
start = 0
end = len(menus) - 1
target = order
while start <= end:
mid = (start + end) // 2
if target == menus[mid]:
results.append(1)
break
elif target < menus[mid]:
end = mid - 1
elif target > menus[mid]:
start = mid + 1
sum = 0
b = False
for result in results:
sum += result
if sum == len(orders):
return True
else:
return False
result = is_available_to_order(shop_menus, shop_orders)
print(result)
주문한 shop_orders의 요소가 한번씩 target이 되어야 한다.
result 리스트를 생성해 만약 주문이 shop_menu에 있으면 1를 append하게 코드를 짜봤다.
다 돌고 나와 result 요소의 합(또는 길이)가 shop_orders의 길이와 같으면 True를 반환한다.
📄 답안 코드
shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]
def is_available_to_order(menus, orders):
menus_set = set(menus)
for order in orders:
if order not in menus_set:
return False
return True
result = is_available_to_order(shop_menus, shop_orders)
print(result)
첫번째 답안코드는 이분탐색 방법은 같으나, 함수를 2개 사용해 푼 방식.
두번째 답안코드는 집합자료 중 중복을 허용하지 않는 set을 활용해 보다 간결하게 코드를 짠 코드!!
숙제3. 더하거나 빼거나
📄 나의 코드
numbers = [2, 3, 1]
target_number = 0
sums = []
def get_all_combinations(numbers, curr_idx, curr_sum):
if curr_idx == len(numbers):
return sums.append(curr_sum)
get_all_combinations(numbers, curr_idx + 1, curr_sum + numbers[curr_idx])
get_all_combinations(numbers, curr_idx + 1, curr_sum - numbers[curr_idx])
return sums
# print(get_all_combinations(numbers, 0, 0)) #[6, 4, 0, -2, 2, 0, -4, -6]
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target):
# 구현해보세요!
list = get_all_combinations(array, 0, 0)
count = 0
for el in list:
if target == el:
count += 1
return count
print(get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number)) # 5를 반환해야 합니다!
(+-)2 (+-)3 (+-)1
총 sums는 2의 3승으로 8가지 경우의 수가 나온다.
이문제를 특강 때 풀어서 겨우 이해!
여기 문제를 쉽게 접근하기 어려운 이유가 numbers맨 처음 요소 앞에 -가 붙을 수 있다는 사실을 가관하기 때문이다!
모든 경우의 수의 합을 sums에 담아 target_number와 비교해 count값을 구하면 된다.
다시 아예 안보고 풀어보는 연습이 필요하다.
📄 답안 코드
numbers = [2, 3, 1]
target_number = 0
result_count = 0 # target 을 달성할 수 있는 모든 방법의 수를 담기 위한 변수
def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
if current_index == len(array): # 탈출조건!
if current_sum == target:
global result_count
result_count += 1 # 마지막 다다랐을 때 합계를 추가해주면 됩니다.
return
get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
current_sum + array[current_index])
get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
current_sum - array[current_index])
get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
print(result_count) # 2가 반환됩니다!
'알고리즘' 카테고리의 다른 글
타임어택 특강 (0) | 2022.12.01 |
---|---|
자료구조 3주차_큐&해쉬 (0) | 2022.11.28 |
자료구조 3주차_스택 (0) | 2022.11.25 |
자료구조 3주차_정렬 (2) | 2022.11.25 |
자료구조 2주차_이진탐색과 재귀함수 (0) | 2022.11.24 |