SWEA 5207 이진탐색 (python)

5207. [파이썬 S/W 문제해결 구현] 4일차 - 이진 탐색 D3

 

 

유사문제

2021.04.21 - [분류 전체보기] - SWEA 4839 이진탐색 (python)

 

문제

서로 다른 정수 N개가 주어지면 정렬한 상태로 리스트 A에 저장한다. 그런 다음 리스트 B에 저장된 M개의 정수에 대해 A에 들어있는 수인지 이진 탐색을 통해 확인하려고 한다.

전체 탐색 구간의 시작과 끝 인덱스를 l과 r이라고 하면, 중심 원소의 인덱스 m=(l+r)//2 이고, 이진 탐색의 왼쪽 구간은 l부터 m-1, 오른쪽 구간은 m+1부터 r이 된다.

이때 B에 속한 어떤 수가 A에 들어있으면서, 동시에 탐색 과정에서 양쪽구간을 번갈아 선택하게 되는 숫자의 개수를 알아보려고 한다.

다음은 10개의 정수가 저장된 리스트 A에서 이진 탐색으로 6을 찾는 예이다.

	0	1	2	3	4	5	6	7	8	9
A	1	2	3	4	5	6	7	8	9	10
	l				m					r	m=4, A[4]=5 < 6 이므로 m의 오른쪽 구간 선택
						l		m		r	m=7, A[7]=8 > 6 이므로 m의 왼쪽 구간 선택
						l,m	r				m=5, A[5]=6으로 찾는 값이므로 탐색 중단

6은 탐색 과정에서 양쪽을 번갈아 가며 선택하게 된다.

예를 들어 10을 찾는 경우 오른쪽-오른쪽 구간을 선택하므로 조건에 맞지 않는다

5를 찾는 경우 m에 위치하므로 조건에 맞는다.

이때 m에 찾는 원소가 있는 경우 방향을 따지지 않는다. M개의 정수 중 조건을 만족하는 정수의 개수를 알아내는 프로그램을 만드시오.

[입력]

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 A와 B에 속한 정수의 개수 N, M이 주어지고, 두 줄에 걸쳐 N개와 M개의 백만 이하의 양의 정수가 주어진다.

1<=N, M<=500,000

[출력]

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

풀이과정

밑에와 같이 풀었더니 10개중 4개만 맞았다. 어느부분이 문제인지 검토해보자

T = int(input())

def binary_search(number, L, R):
    global count
    m = (L+R)//2
    if A[m] == number or A[L] == number or A[R] == number:
        count += 1
        return

    if A[L] < number < A[m] and not visited[0]:
        visited[0] = True
        binary_search(number, L, m)
        visited[0] = False
    elif A[m] < number < A[R] and not visited[1]:
        visited[1] = True
        binary_search(number, m, R)
        visited[1] = False
    else:
        return

for tc in range(1, T+1):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    count = 0
    visited = [0, 0]


    for i in range(M):
        binary_search(B[i], 0, N-1)

    print("#{} {}".format(tc, count))

문제를 찾았다 문제를 보면 m이 도달 해야하는데 나는 그냥 L,R에 걸리면 바로 도출되기 때문에 10같은 경우는 찾았다고 나오는 것 이다. - 사실은 계속 오른쪽으로 가야해서 못찾음

코드

import sys
sys.stdin = open('input.txt')

T = int(input())


for tc in range(1, T+1):
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    # A를 정렬해야 한다고 했으므로 먼저 정렬
    A.sort()
    # 숫자 갯수를 셀 변수 초기화
    cnt = 0
    # B의 원소들을 확인하기 위해서 M으로 B의 길이를 설정
    for i in range(M):
        # 초기 left, right 값 설정
        L = 0
        R = N-1
        # target 변수 설정
        tar = B[i]
        # 그전과정을 저장해주는 변수
        history = 0  # 1:left , 2:right
        # L이 R을 넘어갈 때 까지 검사
        while L <= R:
            # 문제조건에 나온대로 중앙값 설정
            mid = (L+R)//2
            # 만약 중앙값하고 같아진다면 찾은것
            if tar == A[mid]:
                cnt += 1
                break
            # 만약 중앙값 보다 클때 오른쪽으로 가야한다.
            elif tar > A[mid]:
                # 하지만 이미 오른쪽으로 온상태라면
                if history == 2:
                    # 못찾는케이스
                    break
                else:
                    # 아니라면 L을 갱신하고
                    L = mid + 1
                    # 기록하기
                    history = 2
            # 그반대로 작은경우에는 왼쪽으로가야함
            elif A[mid] > tar:
                # 하지만 이미 왼쪽으로 온상태라면 종료
                if history == 1:
                    break
                else:
                    # 아니면 똑같이 해줌
                    R = mid - 1
                    history = 1
    print("#{} {}".format(tc, cnt))

추가

• 사실 진작 푼 문제일건데 계속 코드를 조금씩 수정하고 머릿속으로만 하니까 시간이 너무많이 걸렸다. 테스트 케이스 계속 몇개씩 빵구나고 해서 쓸데없이 시간을 많이 잡아 먹었다.
  • 혹여나 제자리를 맴돌고 있다면 처음부터 다시 접근해 보는것도 하나의 방법
  • 차근차근 케이스를 검토해보자 😂