참고 교재

이것이 코딩테스트다 with 파이썬 (나동빈, 2021)

실전 문제 1 - 부품 찾기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
n = int(input())
stock = list(map(int, input().split()))
m = int(input())
requests = list(map(int, input().split()))

stock.sort()

for target in requests:
    start = 0
    end = len(stock) - 1
    found = False

    while start <= end:
        mid = (start + end) // 2
        if stock[mid] == target:
            print('yes')
            found = True
            break
        elif target < stock[mid]:
            end = mid - 1
        else:
            start = mid + 1

    if found == False:
        print('no')

실전 문제 2 - 떡볶이 떡 만들기

3중 반복문

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
n, m = map(int, input().split())
stock = list(map(int, input().split()))

stock.sort()

height = stock[-1] - 1

length = len(stock)
mid = len(stock) // 2

while height >= 0:
    while mid >= 0 and height < stock[mid]:
        mid -= 1

    x = sum([x - height for x in stock[mid + 1: length]])

    if x >= m:
        print(height)
        break

    height -= 1

이진 탐색

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
n, m = map(int, input().split())
stock = list(map(int, input().split()))

start = 0
end = max(stock)
result = 0

while start <= end:
    total = 0
    mid = (start + end) // 2

    for x in stock:
        if x > mid:
            total += x - mid

    if total >= m:
        result = mid
        start = mid + 1
    else:
        end = mid - 1

print(result)