05-6. 이진 탐색 복습

📝문제1. 프로그래머스 60060번(가사 검색)

- 문제

https://programmers.co.kr/learn/courses/30/lessons/60060

- 코드💻

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

# 모든 단어를 길이마다 나누어서 저장하기 위한 리스트
array = [[] for _ in range(10001)]
# 모든 단어를 길이마다 나누어서 뒤집어 저장하기 위한 리스트
reversed_array = [[] for _ in range(10001)]

def solution(words, queries):
    answer = []
    for word in words: # 모든 단어를 접미사 와일드카드 배열, 접두사 와일드카드 배열에 각각 삽입
        array[len(word)].append(word)  # 단어를 삽입
        reversed_array[len(word)].append(word[::-1])  # 단어를 뒤집어서 삽입
        
    for i in range(10001): # 이진 탐색을 수행하기 위해 각 단어 리스트 정렬 수행
        array[i].sort()
        reversed_array[i].sort()
        
    for q in queries: # 쿼리를 하나씩 확인하며 처리
        if q[0] != '?':  #접미사에 와일드카드가 붙은 경우
            res = count_by_range(array[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
        else: # 접두사에 와일드카드가 붙은 경우
            res = count_by_range(reversed_array[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?','z'))
        # 검색된 단어의 개수를 저장
        answer.append(res)
        
    return answer

---

📝문제2. 백준 17266번(어두운 굴다리)

- 문제

https://www.acmicpc.net/problem/17266

- 코드💻

from sys import stdin
# n : 굴다리의 길이, m : 가로등의 개수, x : m개의 설치할 수 있는 가로등의 위치
n = int(stdin.readline())
m = int(stdin.readline())
array = list(map(int, stdin.readline().split()))

# 가로등이 1개인 경우
if len(array) == 1:
    # 해당 가로등의 위치와 시작점, 끝점과의 두 거리 중 더 큰 값을 높이로 선정
    height = max(array[0] - 0, n - array[0])

# 가로등이 여러 개인 경우
else:
    # 초기 높이 : 시작점과 첫 가로등 사이의 거리
    height = array[0]
    for i in range(len(array)):
        # 끝에 가장 가까운 가로등이 비춰야 할 거리(?)
        if i == (len(array) - 1):
            tmp = n - array[-1]
        else:
            # 마주하는 가로등의 거리 (양 끝의 가로등 제외)
            a = array[i+1] - array[i]
            # 해당 거리를 2로 나눈 나머지가 홀수인 경우
            # 가로등의 높이가 1이 더 높아야만 사이의 모든 거리를 비출 수 있음
            if a % 2:
                tmp = a // 2 + 1
            # 해당 거리를 2로 나눈 나머지가 짝수인 경우
            else:
                tmp = a // 2
        height = max(height, tmp)

print(height)

---

📝문제3. 백준 13702번(이상한 술집)

- 문제

https://www.acmicpc.net/problem/13702

- 코드💻

from sys import stdin
n, k = map(int, stdin.readline().split())
array = []
for _ in range(n):
    array.append(int(stdin.readline()))
array.sort()

start, end = 0, max(array)
result = 0
while start <= end:
    mid = (start + end) // 2
    count = 0
    for x in array:
        a = x // mid
        count += a
    if count < k:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

---

새로운 문제를 풀기보다는 어려웠던 문제들을 다시 풀고 따라쳐보며 복습해봤다!