1. 배달 가능 여부

문제

Q. 배달의 민족 서버 개발자로 입사했다.
상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다.

그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.

menus = ["떡볶이", "만두", "오뎅", "사이다", "콜라"]
orders = ["오뎅", "콜라", "만두"]

해결 방안

shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]


def is_available_to_order(menus, orders):
    menus_set = set(menus)				# O(N)
    for order in orders:				# O(M)
        if order not in menus_set:		# O(1)	
            return False
    return True


result = is_available_to_order(shop_menus, shop_orders)
print(result)


# 시간 복잡도는 O(N + M)
# list 대신 set으로 설정하여 시간 복잡도 O(1)이 나옴, list는 O(N)

2. LinkedList의 끝에서 k번째 값 구하기

문제

[6] - [7] - [8] 이런 링크드 리스트에서 끝에서 2번째 값 구하기
				-> [7]

해결 방안

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):
        length = 1
        cur = self.head

        while cur.next is not None:
            cur = cur.next				# 한칸씩 뒤로가기
            length += 1                 # 전체 길이 알아내기
        end_length = length - k         # 끝에서 k번째

        cur = self.head
        for i in range(end_length):		# k번째까지 감
            cur = cur.next
        return cur

linked_list = LinkedList(6)				# [6]-[7]-[8]
linked_list.append(7)					#  3   2   1  뒤에서
linked_list.append(8)

print(linked_list.get_kth_node_from_last(2).data) 

3. 더하거나 빼서 원하는 값을 도출해내는 경우의 수(재귀)

문제

[2, 3, 1] 에서 숫자들을 조합하여 0이 나오는 경우의 수

+2 -3 +1 = 0
-2 +3 -1 = 0  -> 2가지

numbers = [2, 3, 1]
target_number = 0

해결 방안

numbers = [2, 3, 1]
target_number = 0

# N의 길이의 배열에서 더하거나 뺀 모든 경우의 수는
# N-1 길이의 배열에서 마지막 원소를 더하거나 뺀 경우의 수를 추가하면 됨

# 1. +2 +3    +1 or -1     -> 2가지 (+2+3+1, +2+3-1)
# 2. +2 -3    +1 or -1     -> 2가지 (+2-3+1, +2-3-1) 
# 3. -2 +3    +1 or -1     -> 2가지 (-2+3+1, -2+3-1)
# 4. -2 -3    +1 or -1     -> 2가지 (-2-3+1, -2-3-1)  총 8가지


# 2, 3, 1
# current_index = 0
# current_sum = 0
# all_ways = result = []

1. 모든 경우 구하기
result = []
def get_all_ways(array, current_index, current_sum, all_ways):
     if current_index == len(array):   # 탈출조건
         all_ways.append(current_sum)    # 마지막 index일 때 합계를 추가해줌
         return

     get_all_ways(array, current_index + 1, current_sum + numbers[current_index], all_ways)
     # (array, 1, 0 + 2, all_ways)
     get_all_ways(array, current_index + 1, current_sum - numbers[current_index], all_ways)
     # (array, 1, 0 - 2, all_ways)

 print(get_all_ways(numbers, 0, 0, result))  none
 print(result)								 [6, 4, 0, -2, 2, 0, -4, -6]
 
 
 
2. 해당하는 경우의 수 구하기
result_count = 0 
def get_target_ways(array, target, current_index, current_sum):
     if current_index == len(array):   # 탈출조건
         if current_sum == target:
         	global result_count
         	result_count += 1
         return

     get_target_ways(array, target, current_index + 1, current_sum + numbers[current_index])
     # (array, 1, 0 + 2)
     get_target_ways(array, target, current_index + 1, current_sum - numbers[current_index])
     # (array, 1, 0 - 2)

 print(get_target_ways(numbers, 0, 0, result))  none
 print(result_count)							2 (0이 나온는 경우)			
 

추가

엇!! 그런데 result_count 가 0으로 찍힙니다!! 

왜일까요?
그 이유는 바로 파이썬의 Call by Object Reference  라는 개념 때문에 그렇습니다.

함수에서 파라미터로 배열을 넘기면 그 내부에 원소를 추가하거나 할 수 있는데
파라미터로 int, str 타입의 변수를 넘기면 그 값이 복제되어 새로운 값을 생성합니다.

따라서 함수 내부의 all_ways_count 만 변경이 되고,
함수 외부의 result_count 는 변하지 않아서 문제가 생깁니다!

이런 경우에는, 함수 외부의 변수를 사용하기 위해 
파이썬의 글로벌 변수라는 걸 사용하시면 됩니다!

외부에 정의되어 있는 변수를 내부에서 사용하기 위해서
global 변수이름 이라고 쓰기만 하면 됩니다! 

all_ways_count 파라미터는 안 쓰니까 지워주면 되겠죠~!