[파이썬] 4839. 이진탐색

swexpertacademy.com/main/learn/course/lectureProblemViewer.do

SW Expert Academy

 

※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.

코딩반 학생들에게 이진 탐색을 설명하던 선생님은 이진탐색을 연습할 수 있는 게임을 시켜 보기로 했다.

짝을 이룬 A, B 두 사람에게 교과서에서 각자 찾을 쪽 번호를 알려주면, 이진 탐색만으로 지정된 페이지를 먼저 펼치는 사람이 이기는 게임이다.

예를 들어 책이 총 400쪽이면, 검색 구간의 왼쪽 l=1, 오른쪽 r=400이 되고, 중간 페이지 c= int((l+r)/2)로 계산한다.

찾는 쪽 번호가 c와 같아지면 탐색을 끝낸다.

A는 300, B는 50 쪽을 찾아야 하는 경우, 다음처럼 중간 페이지를 기준으로 왼쪽 또는 오른 쪽 영역의 중간 페이지를 다시 찾아가면 된다.

	A	B
첫 번째 탐색	l=1, r=400, c=200	l=1, r=400, c=200
두 번째 탐색	l=200, r=400, c=300	l=1, r=200, c=100
세 번째 탐색		l=1, r=100, c=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

 

👻 나의 풀이

 

T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    p, A, B = map(int, input().split())  	# 전체 쪽수, A와 B가 각각 찾을 쪽 번호
    p_A = [1, p, 0, A]			# 왼쪽, 오른쪽, 중간 페이지, 목표 페이지
    p_B = [1, p, 0, B]

    def binary_search(lst):
        cnt = 0						# 탐색 횟수
        while True:
            lst[2] = int((lst[0] + lst[1]) / 2)  	# 중간 페이지
            cnt += 1
            if lst[2] < lst[3]:  	# 중간 페이지와 목표 페이지 비교
                lst[0] = lst[2]  	# 왼쪽을 목표 페이지로 바꿈
            elif lst[2] > lst[3] :
                lst[1] = lst[2]  	# 오른쪽에 중간 페이지 할당
            else:
                break				# 목표 페이지를 펼치면 break
        lst.append(cnt)

    binary_search(p_A)				# 함수 호출
    binary_search(p_B)
	
    # 탐색 횟수가 더 작은 쪽을 출력('A' or 'B') 비기면 0
    if p_A[-1] < p_B[-1]:
        result = 'A'
    elif p_A[-1] == p_B[-1]:
        result = 0
    else:
        result = 'B'
        
    print('#%d %s' %(test_case, result))

 

나랑 알고리즘은 같은데 내가 뭘 잘못했는지 시간 초과...

pycharm으로 디버그하면서 잘못된 점을 고쳤다. 

1. 리스트 p_A와 p_B를 할당할 때 인덱스3에 중간 페이지 값을 p//2로 넣어주고 시작했었다. cnt도 1로.

2. while문내에서 if lst[2] == lst[3] : break를 첫 문장에 썼는데 디버그 중에 else로 넣어야된다는 것을 알았다.

3. break문 밑으로 if조건문들을 썼다(identation 실수)

 

🐾 다른사람 풀이

 

def BS(page, target):  # 이진 탐색
    l = 1		# 왼쪽
    r = page	# 오른쪽
    cnt = 0		# 이진 탐색 횟수
    while(r - l > 1): 		# 두 장 이하로 남으면 탈출
        c = (l+r)//2  		# int((l+r)/2)와 같음
        cnt += 1  # 번째 시도
        if target < c:
            r = c
        elif target > c:
            l = c
        else:  # target == c
            break
    if l + 1 == r:  # 두 장 남은 경우
        cnt += 1 # 찾음
    return cnt


T = int(input())

for test_case in range(1, T + 1):
    P, Pa, Pb = map(int, input().split())	# 전체 쪽수, A와 B가 각각 찾을 쪽 번호
    cnt_a = BS(P, Pa)
    cnt_b = BS(P, Pb)
    
    result = 0
    if cnt_a < cnt_b:
        result = 'A'
    elif cnt_a > cnt_b:
        result = 'B'
        
    print('#{} {}'.format(test_case, result))

 

알고리즘이 나랑 같다.

함수의 매개변수로 전체 쪽수, 목표 페이지만 넣은 것이 나랑 다르다.

나도 함수를 깔끔하게 바깥으로 뺄걸..