[이것이 취업을 위한 코딩테스트이다 with 파이썬] Ch.15 이진 탐색 문제

📌한 장으로 보는 알고리즘

✔️ bisect 클래스란?

 - 사용 조건 : '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적

 - 가장 중요한 함수 & 시간복잡도

• bisect_left(a,x) : (정렬된 순서를 유지하면서) 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• bisect_right(a,x) : (정렬된 순서를 유지하도록) 리스트 a에 데이터x를 삽입할 가장 오른쪽 인덱스 찾는 메서드
• 시간 복잡도 : O(logN)

- 예시 

from bisect import bisect_left, bisect_right

a = [1,2,4,4,8]
x = 4

print(bisect_left(a,x)) 	# 2
print(bisect_right(a,x))	# 4

 - 효과적인 사용

• '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구하고자 할 때, 효과적으로 사용

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

a = [1,2,3,3,3,3,4,4,8,9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))    # 2

# 값이 [-1,3] 범위에 있는 데이터 개수 출력
print(count_by_range(a,-1,3))   # 6

이진탐색
 - 조건 : 배열 내부 데이터가 정렬되어 있어야 함 
 - 방법 : 탐색 범위를 반으로 줄여가며 데이터 탐색 (시작점, 끝점, 중간점 이용)

bisect 클래스
 - 사용 조건 : 정렬된 배열에서 특정한 데이터를 찾도록 요구하는 문제일 때

---

📌Q.27) 정렬된 배열에서 특정 수의 개수 구하기

✔️문제

N개의 원소를 포함하는 수열, 오릅차순으로 정렬.

해당 수열에서 x가 등장하는 횟수 계산 

(단, 시간복잡도 O(logN)으로 알고리즘 설계해야 '시간초과' 판정을 안 받음)

 

ex) 수열 [1,1,2,2,2,2,3], x = 2 → 4 출력

 

✔️입력 조건

• 첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
  (1 <= N <= 1,000,000), (-10**6 <= x <= 10*9)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
  (-10**9 <= 각 원소의 값 <= 10**9)

 

✔️출력 조건

• 수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

 

✔️입출력 예시

 

✔️나의 문제풀이

from bisect import bisect_left, bisect_right

n,x = map(int,input().split())
list_n = list(map(int,input().split()))

left_index = bisect_left(list_n, x)
right_index = bisect_right(list_n,x)

if right_index - left_index > 0:
    print(right_index - left_index)
else:
    print(-1)

 

✔️책 문제풀이

1) 이진탐색 이용하기

- 아이디어 : x가 처음 등장하는 인덱스, x가 마지막으로 등장하는 인덱스를 각각 계산 → 이진탐색 함수 2개 작성

• 이진 탐색을 요구하는 고난이도 문제에 사용하는 테크닉
• 잘 이해해 두기

def count_by_value(array, x):
    n = len(array)

    # x가 처음 등장한 인덱스 계산
    a = first(array, x, 0, n-1)

    # 수열에 x가 존재하지 않는 경우
    if a == None:
        return 0
    
    b = last(array, x, 0, n-1)

    return b - a + 1

def first(array, target, start, end):
    if start > end:
        return None
    
    mid = (start+end) // 2
    
    # 해당 값을 가지는 원소 중, 가장 왼쪽에 있는 경우에만 인덱스 반환
    if (mid == 0 or target > array[mid-1]) and array[mid] == target:
        return mid
    elif array[mid] >= target:
        return first(array, target, start, mid-1)
    else:
        return first(array, target, mid+1, end)
    
def last(array, target, start, end):
    if start > end:
        return None
    
    mid = (start+end) // 2

    if (mid == n-1 or array[mid+1] > target) and array[mid] == target:
        return mid
    elif array[mid] > target:
        return last(array, target, start, mid - 1)
    else:
        return last(array, target, mid + 1, end)
    

n,x = map(int,input().split())
array = list(map(int,input().split()))

count = count_by_value(array,x)

if count == 0:
    print(-1)
else:
    print(count)

2) bisect 라이브러리 이용

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

n,x = map(int,input().split())
a = list(map(int,input().split()))

count  = count_by_range(a, x,x)

if count == 0:
    print(-1)
else:
    print(count)

 

✔️리뷰

- array[mid]와 target이 동일해지는 조건 잘 설정하기

---

📌Q.28) 고정점 찾기

✔️문제

고정점 - 수열의 원소 중, 그 값이 인덱스와 동일한 원소

ex) a = [-15, -4, 2, 8, 13] 일 때, a[2] = 2 → 고정점은 2

 

하나의 수열이 N개의 서로 다른 원소 포함, 모든 원소가 오름차순으로 정렬.

수열에 고정점이 있다면, 고정점을 출력하는 프로그램 작성하기 (고정점은 최대 1개만 존재)

고정점이 없다면 -1을 출력

(단, 시간복잡도 O(logN)으로 알고리즘 설계해야 '시간초과' 판정을 안 받음)

 

✔️입력 조건

• 첫째 줄에 N이 입력됩니다.(1<= N <= 1,000,000)
• 둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
  (-10**9 <= 각 원소의 값 <= 10**9)

 

✔️출력 조건

• 고정점을 출력한다. 고정점이 없다면 -1을 출력합니다.

 

✔️입출력 예시

 

✔️나의 문제풀이

- 고정점의 비교는 mid와 array[mid]를 이용

• mid > array[mid] : 뒷 부분 탐색으로 start = mid + 1로 수정
• mid < array[mid] : 앞 부분 탐색으로 end = mid - 1로 수정

def binary_search(array, start, end):
    if start > end:
        return -1
    
    mid = (start+end) // 2

    if mid == array[mid]:
        return mid
    elif mid > array[mid]:
        return binary_search(array, mid+1, end)
    else:
        return binary_search(array, start, mid-1)
    

n = int(input())
array = list(map(int,input().split()))

print(binary_search(array, 0, n-1))

 

✔️책의 문제풀이

- 나의 문제풀이와 동일

def binary_search(array, start, end):
    if start > end:
        return None
    
    mid = (start+end) // 2

    if mid == array[mid]:
        return mid
    elif mid < array[mid]:
        return binary_search(array, start, mid-1)
    else:
        return binary_search(array, mid+1, end)
    

n = int(input())
array = list(map(int,input().split()))

index = binary_search(array, 0, n-1)

if index == None:
    print(-1)
else:
    print(index)

---

📌Q.29) 공유기 설치

✔️문제 유형

 

✔️문제

2110번: 공유기 설치

 

✔️나의 문제풀이

X

 

✔️책의 문제풀이

- 아이디어: 이진탐색으로 '가장 인접한 두 공유기 사이의 거리' 조절 → 매 순간 실제로 공유기를 설치하여 C보다 많은 개수로 공유기를 설치할 수 있는지 체크 → (C보다 많은 개수로 공유기 설치 가능) '가장 인접한 두 공유기 사이의 거리'값 증가, 더 큰 값도 성립하는지 확인 위해 탐색 수행

- 파라메트릭 서치 유형

n,c = map(int,input().split())

array = []
for i in range(n):
    array.append(int(input()))

array.sort()

start = array[1] - array[0]
end = array[-1] - array[0]
result = 0

while start <= end:
    mid = (start+end) // 2
    value = array[0]
    count = 1

    for i in range(1,n):
        if array[i] >= value + mid:
            count += 1
            value = array[i]

    if count >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1


print(result)

 

✔️리뷰

- 거리와 공유기 설치 한 번에 해결해야 함

---

📌Q.30) 가사 검색 

 

✔️문제

프로그래머스

 

✔️나의 문제풀이

- 정확성은 모두 통과, 효율성 3/5 → 시간 초과(55/100)

def comparison(word):
    nums = []
    for i in range(len(word)):
        if word[i] == '?':
            nums.append(i)
    
    if nums[0] == 0:
        return nums[-1] + 1, len(word) - 1
    else:
        return 0, nums[0] - 1
    
    
def solution(words, queries):
    answer = []
    
    for i in range(len(queries)):
        start, end = comparison(queries[i])
        ans = 0
        for j in range(len(words)):
            if (len(words[j]) == len(queries[i])) and (words[j][start:end+1] == queries[i][start:end+1]):
                ans += 1
        answer.append(ans)
    
    return answer

- 이진탐색으로 바꿔도 시간초과, 결과 동

def front(word, start, end):
    if start > end :
        return start , len(word) - 1
    
    mid = (start+end) // 2
    
    if (start != 0 and word[start - 1] == '?' and word[start] != '?'):
        return start, len(word) - 1
    elif word[start] == '?' and word[mid] == '?':
        return front(word, mid + 1, end)
    elif word[start] == '?' and word[mid] != '?':
        return front(word, start, mid - 1)
    
def back(word, start, end):
    if start > end :
        return 0, end
    
    mid = (start+end) // 2
    
    if (end != len(word) - 1 and word[end + 1] == '?' and word[end] != '?'):
        return 0, end
    elif word[mid] == '?' and word[end] == '?':
        return back(word, start, mid - 1)
    elif word[mid] != '?' and word[end] == '?':
        return back(word, mid + 1, end)
        
    
    
    
def solution(words, queries):
    answer = []
    # return back(queries[3], 0, len(queries[3])-1)
    for i in range(len(queries)):
        if queries[i][0] == '?':
            start, end = front(queries[i], 0, len(queries[i])-1)
        else:
            start, end = back(queries[i], 0, len(queries[i])-1)
        ans = 0
        for j in range(len(words)):
            if (len(words[j]) == len(queries[i])) and (words[j][start:end+1] == queries[i][start:end+1]):
                ans += 1
        answer.append(ans)
    
    return answer

 

✔️책의 문제풀이

 - 아이디어 : 각 단어를 길이에 따라 나눔 → 모든 리스트 정렬 →각 쿼리에 대해 이진탐색을 수행

• "fro??"에서 "fro"의 시작되는 단어 위치, 끝나는 단어 위치 찾기
• "fro??"를 "froaa" 보다 크거나 같음 "frozz"보다 작거나 같은 단어의 개수 세도록 구현
• 접두사?인 경우 : 뒤집힌 단어 리스트를 대상으로 이진탐색 수

명확히 이해 안감..! 더 고민해보

from bisect import bisect_left, bisect_right

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

 

✔️리뷰

 - bisect 문자열도 가능 (특수문자는 안되서 ?에 문자를 넣은듯) 

 - 모든 길이마다 따로 리스트에 저장하는 방법 사용해도 시간초과 안 남

 - 접두사는 뒤집어서 저장하기!!!! 

 - 이진탐색은 정렬되어 있어야 함!