[문제실습] Ch 7. Search

자세한 설명은 아래 포스트를 참고하기
masso.tistory.com/80?category=891816

1. 부품 찾기

: 다른 input 만드느라 애 좀 먹었다..ㅠㅜ

 

1-0. input & output

# input 1
N, M = 5, 3
store, client = [8, 3, 7, 9, 2], [5, 7, 9]
# ouput 1
# no yes yes

# input 2
N, M = 50, 20
store = [73,15,26,59,49,44,8,47,63,74,66,81,67,41,52,45,57,4,51,12,10,37,64,7,48,23,42,18,71,55,36,61,83,82,2,20,94,76,28,58,50,92,79,70,96,19,54,97,40,86]
client = [4,35,20,53,93,6,63,52,21,41,5,77,91,78,79,7,46,39,64,95]
# output 2
# yes no yes no no no yes yes no yes no no no no yes yes no no yes no

# input 3
N, M = 60, 60
store = [911,643,184,439,855,981,950,776,519,204,321,47,749,53,851,272,970,270,42,137,523,251,990,171,487,860,796,19,841,46,799,215,333,766,214,709,687,299,334,554,991,396,163,473,869,76,549,128,821,756,703,463,60,283,706,81,314,415,517,375]
client = [500,923,351,303,489,294,579,708,287,382,137,906,229,788,332,251,862,486,795,638,932,725,573,541,329,177,324,868,710,277,290,909,948,364,87,727,652,497,977,618,532,258,949,632,687,29,735,580,617,770,70,946,569,743,189,388,322,636,61,200]
# output 3
# no no no no no no no no no no yes no no no no yes no no no no no no no no no no no no no no no no no no no no no no no no no no no no yes no no no no no no no no no no no no no no no

 

1-1. 정렬한 후 이진 탐색 binary Search

'''=== way1. binary search ==='''
def binary_search(target, start, end, arr):
    if start > end:
        return False
    mid = (start + end) // 2 # 괄호가 없으면 우선 순위가 달라짐
    if arr[mid] == target:
        return True
    elif target < arr[mid]:
        return binary_search(target, start, mid-1, arr) # -1 자꾸 까먹음..!
    else:
        return binary_search(target, mid+1, end, arr) # +1 자꾸 까먹음..!

start_time = timeit.default_timer()
store = sorted(store)
for target in client:
    if binary_search(target, 0, N-1, store):
        print("yes", end = ' ')
    else: 
        print("no", end = ' ')
print()
end_time = timeit.default_timer()
print(">> binary_search time: ", end_time - start_time)

 

1-2. set의 성질 이용하기

'''=== way2. set() ==='''
# N = int(input())
# store = set(map(int, input().split())) #!! list 대신 set으로!
# M = int(input())
# client = list(map(int, input().split()))

set_store = set(store)
start_time = timeit.default_timer()
for target in client:
    if target in set_store:
        print("yes", end = ' ')
    else:
        print("no", end = ' ')
end_time = timeit.default_timer()

 

1-3. 계수 정렬(생략)

 

2. 떡볶이 떡 만들기

: 손님이 원하는 길이에 딱 맞는 최대 높이를 찾을 수 없다면,
  손님이 원하는 길이보다 더 많이 주는 높이 중에서 최댓값을 반환해야한다!! (아래 input 2,3 참고)

 

2-0. input

# input 1
# N, M = 4, 6
# rice_cakes = [19, 15, 10, 17]
# answer:15

# input 2
# N, M = 50, 456
# rice_cakes = [693, 124, 802, 928, 882, 939, 375, 944, 810, 860, 310, 110, 851, 433, 888, 957, 574, 320, 673, 389, 
# 594, 807, 809, 946, 949, 138, 688, 136, 581, 398, 649, 225, 188, 301, 743, 299, 623, 220, 643, 767, 588, 183, 551, 
# 264, 184, 547, 376, 766, 811, 162]
'''절단기에 설정할 수 있는 높이의 최댓값:  872
>> sequential_search time:  0.0007, >> recursive_binary_search time:  0.0003, >> while_binary_search time:  0.0003
'''

# input 3
N, M = 200, 1357
rice_cakes = [273, 20, 157, 49, 24, 224, 175, 193, 169, 153, 141, 297, 258, 287, 268, 154, 211, 185, 113, 294, 129, 117, 242, 91, 
122, 106, 215, 292, 271, 188, 56, 167, 256, 63, 172, 206, 213, 51, 249, 146, 54, 124, 97, 198, 264, 200, 197, 156, 209,
13, 252, 62, 152, 236, 27, 207, 160, 277, 10, 176, 241, 223, 46, 274, 205, 262, 22, 291, 293, 132, 11, 253, 41, 283, 
199, 110, 126, 36, 71, 105, 220, 87, 231, 31, 171, 128, 263, 270, 30, 95, 281, 183, 155, 260, 216, 135, 44, 257, 276, 
104, 254, 279, 217, 12, 299, 55, 149, 138, 58, 125, 246, 266, 66, 201, 75, 85, 57, 77, 229, 101, 133, 21, 35, 161, 240,
286, 131, 290, 99, 130, 88, 184, 261, 247, 83, 151, 84, 238, 81, 221, 267, 265, 89, 173, 123, 245, 79, 26, 102, 225, 
278, 219, 186, 144, 68, 166, 180, 120, 162, 118, 52, 25, 139, 45, 50, 43, 163, 17, 86, 255, 168, 140, 181, 28, 96, 53,
112, 233, 109, 70, 237, 196, 248, 80, 232, 159, 111, 100, 275, 194, 78, 251, 272, 295, 76, 94, 289, 174, 47, 202]
'''절단기에 설정할 수 있는 높이의 최댓값:  240
>> sequential_search time:  0.0011, >> recursive_binary_search time:  0.0005, >> while_binary_search time:  0.0006
'''
# answer = 240

 

2-1. 순차 탐색 sequential Search

'''sequential_search'''
def sequential_search(arr):
    max_H = max(arr)
    while max_H > 0:
        total = 0
        for ele in arr:
            if ele > max_H:
                total += ele - max_H
        if total >= M:
            print("절단기에 설정할 수 있는 높이의 최댓값: ", max_H)
            break;
        max_H -= 1
            
'''%% 입력의 범위가 최대 10억까지의 정수이므로 시간 초과를 받는다.'''  
start_time = timeit.default_timer()
sequential_search(rice_cakes)
end_time = timeit.default_timer()
print(">> sequential_search time: ", format(end_time - start_time, ".4f"))

 

2-2. 이진 탐색 binary Search

'''binary_search'''
def binary_search(ans, arr, minH, maxH):
    global result
    if minH > maxH:
        return -1
    midH = (minH + maxH) // 2
    total = 0
    for ele in arr:
        if ele > midH:
            total += ele - midH
    if total >= ans:
        result = midH
        return binary_search(ans, arr, midH+1, maxH)
    elif total < ans:
        return binary_search(ans, arr, minH, midH-1)

start_time = timeit.default_timer()
result = 0
binary_search(M, rice_cakes, 0, max(rice_cakes))
print("절단기에 설정할 수 있는 높이의 최댓값: ", result)
end_time = timeit.default_timer()
print(">> recursive_binary_search time: ", format(end_time - start_time, ".4f"))