자료구조 2주차 복습&숙제

자료구조 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가 반환됩니다!