[SWEA] 4839. 이진탐색 - Python

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVF-WqqecDFAWg&contentType=PROBLEM&lectureSeq=7&progressVal=0&lastPosition=0&lastPosition2=0&contestProbId=AWTLcyA6qAMDFAVT&kataId=&movieEndYN=N&progressLectureSeq=6&progressContentType=PROBLEM&description= 

SW Expert Academy

 

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

짝을 이룬 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을 출력한다.

< ❓ 생각 >

이진검색

검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행

< 💻 코드 >

1.

def Search(all_page, page):
    start = 1
    end = all_page
    # 탐색 수
    result = 0

    while start <= end:
        middle = int((start + end) // 2)
        # 중앙값과 찾는 값이 같으면 return
        if middle == page:
            result += 1
            return result
        # 찾는 값이 중앙값보다 크면 시작값 = 중앙값
        elif middle < page:
            start = middle
            result += 1
        # 찾는 값이 중앙값보다 작으면 마지막값 = 중앙값
        else:
            end = middle
            result += 1

# T :  테스트 케이스 수
T = int(input())
for tc in range(1,T+1):
    # P : 책의 전체 쪽 수, A : A가 찾을 쪽 번호, B : B가 찾을 쪽 번호
    P, A, B = map(int,input().split())

    # A 탐색수
    a = Search(P,A)
    # B 탐색수
    b = Search(P,B)

    # 탐색수가 더 작은 값이 이김 -> 결과도출
    if a < b:
        print(f'#{tc} A')
    elif b < a:
        print(f'#{tc} B')
    else:
        print(f'#{tc} 0')

2. 재귀

# result : 탐색 수
def Search(page, start, end, result):
    if start > end: # 검색 실패
        return False
    else:
        middle = (start + end) // 2
        if page == middle: # 검색 성공
            result += 1
            return result
        elif page < middle:
            result += 1
            return Search(page, start, middle, result)
        elif page > middle:
            result += 1
            return Search(page, middle, end, result)

# T :  테스트 케이스 수
T = int(input())
for tc in range(1,T+1):
    # P : 책의 전체 쪽 수, A : A가 찾을 쪽 번호, B : B가 찾을 쪽 번호
    P, A, B = map(int,input().split())

    # A 탐색수
    a = Search(A,1,P,0)
    # B 탐색수
    b = Search(B,1,P,0)
  
    # 탐색수가 더 작은 값이 이김 -> 결과도출
    if a < b:
        print(f'#{tc} A')
    elif b < a:
        print(f'#{tc} B')
    else:
        print(f'#{tc} 0')