이진탐색 Python(SW Expert Academy)

난이도 : D2

문제번호 : 4839

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVF-WqqecDFAWg#

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

코딩반 학생들에게 이진 탐색을 설명하던 선생님은 이진탐색을 연습할 수 있는 게임을 시켜 보기로 했다. 짝을 이룬 A, B 두 사람에게 교과서에서 각자 찾을 쪽 번호를 알려주면, 이진 탐색만으로 지정된 페이지를 먼저 펼치는 사람이 이기는 게임이다. 예를 들어 책이 총 400쪽이면, 검색 구간의 왼쪽 l=1, 오른쪽 r=400이 되고, 중간 페이지 c= int((l+r)/2)로 계산한다. 찾는 쪽 번호가 c와 같아지면 탐색을 끝낸다. A는 300, B는 50 쪽을 찾아야 하는 경우, 다음처럼 중간 페이지를 기준으로 왼쪽 또는 오른 쪽 영역의 중간 페이지를 다시 찾아가면 된다. 책의 전체 쪽수와 두 사람이 찾을 쪽 번호가 주어졌을 때, 이진 탐색 게임에서 이긴 사람이 누구인지 알아내 출력하시오. 비긴 경우는 0을 출력한다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다.  1<=T<=50   테스트 케이스 별로 책의 전체 쪽 수 P, A, B가 찾을 쪽 번호 Pa, Pb가 차례로 주어진다. 1<= P, Pa, Pb <=1000

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, A, B, 0 중 하나를 출력한다.

예시

입력	출력
3 400 300 350 1000 299 578 1000 222 888	#1 A #2 0 #3 A

---

2. 문제풀이

이진탐색을 연습하는 문제였다. (파이썬 2일차 문제) 간단하게 목표까지 찾는횟수를 리턴하는 이진탐색하는 함수를 만들어 풀었다. 찾는값이 중간값보다 크다면 시작값을 중간값으로 대체하고 작다면 끝값을 중간값으로 바꾸며 계산하였다. 나중에 찾은 횟수를 비교하여 결과를 리턴하면 끝이난다.

---

3. 소스코드

#D2 4839 이진탐색
def binaryserch(p, key):
    start = 1
    end = p
    count = 0
    while start <= end:
        index = (start+end) // 2
        count += 1
        if index == key:
            return count
        elif index < key:
            start = index
        elif index > key:
            end = index
    return -1
 
T = int(input())
for t in range(1, T+1):
    p, a, b = map(int, input().split())
    a_c = binaryserch(p, a)
    b_c = binaryserch(p, b)
    result = ''
    if a_c < b_c:
        result = 'A'
    elif a_c > b_c : 
        result = 'B'
    else:
        result = '0'
    print("#{} {}".format(t, result))