SWEA 5207 이진탐색

문제

이진 탐색

좌우를 순서대로 반복하며 이진 탐색을 하는 값을 찾아내자

---

풀이

1. flag 변수를 선언해 왼쪽 탐사 및 오른쪽 탐사를 체크한다.
2. flag 변수가 연속으로 True, 혹은 False면 좌우 반복 탐사 조건에 맞지 않는 것이다.
3. 좌우를 반복 탐사하며 target을 발견하면 count 변수를 1씩 증가한다.

---

코드

import sys
sys.stdin = open('sample_input.txt')
T = int(input())

flag = None  # 왼쪽 탐사 시 True 오른쪽 탐사 시 False

def binary_search(target, start, end, data, f):
    mid = (start + end) // 2
    if data[mid] > target:
        f = False  # target이 왼쪽에 있으면 우선 False를 부여해 루프를 돌 수 있게 한다.
    else:
        f = True  # target이 오른쪽에 있으면 우선 True를 부여
        
    while start <= end:
        mid = (start + end) // 2
        if data[mid] == target:  # 원하는 조건에 맞게 target이 존재하므로 True 반환하며 루프 종료
            return True  
        
        elif data[mid] > target:  # 왼쪽 탐사
            if f:  # 왼쪽 탐사 시 flag = True이므로 f = True인 상황에서 또 왼쪽 탐사를 시도하면 False 반환
                return False
            else:  # 오른쪽 탐사 후 왼쪽 탐사를 하는 것이므로 end 값 update 및 flag True 변환
                end = mid - 1
                f = True
            
        else:  # 오른쪽 탐사
            if not f:  # 오른쪽 탐사 시 flag = False 이므로 f = False인 상황에서 또 오른쪽 탐사를 시도하면 False 반환
                return False 
            else:  # 왼쪽 탐사 후 오른쪽 탐사를 하는 것이므로 start 값 update 및 flag False 변환
                start = mid + 1   
                f = False
                

for tc in range(1, T+1):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A.sort()
    B = list(map(int, input().split()))
    
    cnt = 0
    for b in B:
        if b != A[(len(A)-1)//2]:
            if binary_search(b, 0, len(A)-1, A, flag):
                cnt += 1    
                
        else:  # 중앙값과 타겟이 같으므로 바로 cnt를 1 증가시키고 continue
            cnt += 1
        
    print("#{} {}".format(tc, cnt))

        

---

결과

• 처음에 메모리 초과가 떴다. 그래서 이진 탐색 함수를 재귀를 사용했다가 반복문 사용으로 바꾸니 통과가 됐다.
• A 리스트를 sorting 할 때 그냥 sort 메서드를 사용했는데, 앞으론 merge sort나 quick sort를 직접 구현해야겠다.