이진탐색 Python(SW Expert Academy)

난이도 : D3

문제번호 : 5207

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

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

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

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYFsQq11kDFAVT

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

서로 다른 정수 N개가 주어지면 정렬한 상태로 리스트 A에 저장한다. 그런 다음 리스트 B에 저장된 M개의 정수에 대해 A에 들어있는 수인지 이진 탐색을 통해 확인하려고 한다. 전체 탐색 구간의 시작과 끝 인덱스를 l과 r이라고 하면, 중심 원소의 인덱스 m=(l+r)//2 이고, 이진 탐색의 왼쪽 구간은 l부터 m-1, 오른쪽 구간은 m+1부터 r이 된다. 이때 B에 속한 어떤 수가 A에 들어있으면서, 동시에 탐색 과정에서 양쪽구간을 번갈아 선택하게 되는 숫자의 개수를 알아보려고 한다. 다음은 10개의 정수가 저장된 리스트 A에서 이진 탐색으로 6을 찾는 예이다.

예를 들어 10을 찾는 경우 오른쪽-오른쪽 구간을 선택하므로 조건에 맞지 않는다 5를 찾는 경우 m에 위치하므로 조건에 맞는다. 이때 m에 찾는 원소가 있는 경우 방향을 따지지 않는다. M개의 정수 중 조건을 만족하는 정수의 개수를 알아내는 프로그램을 만드시오.

 

입력

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

출력

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

예시

입력	출력
3 3 3 1 2 3 2 3 4 3 5 1 3 5 2 4 6 8 10 5 5 1 3 5 7 9 1 2 3 4 5	#1 2 #2 0 #3 3

---

2. 문제풀이

이분탐색을 할줄안다면 쉽게 풀 수 있는 문제이다. 주의해야 할 점은 예시를 보면 들어오는 값이 정렬되어 들어오는 것처럼 보인다. 그렇지만 결과를 제출할때 정렬이 되지않게 들어오는 경우가 있었다. 그리고 문제를 잘 읽어본다면 실수를 하지 않겠지만 한방향으로 계속 진행하면 진행을 멈춰야 한다. 즉, 왼쪽 오른쪽을 혹으 오른쪽 왼쪽을 번갈아 가면서 진행해야만 계속 진행이 되는것이다. 이렇게 주의하며 코드를 짜면 아래와 같이 나오게 된다.

---

3. 소스코드

 

#D3 5207 이진탐색
 
for t in range(int(input())):
    answer = 0
    N, M = map(int, input().split())
    # 이분탐색은 정렬을 기본조건으로 한다.
    A = sorted(list(map(int, input().split())))
    B = list(map(int, input().split()))
    for b in B:
        # 중간을 탐색하기 때문에 최소점과 최대점을 잡아준다.
        min_idx = 0
        max_idx = N - 1
        # 왼쪽으로 갔는지 오른쪽으로 갔는지 체크하기 위한 용도
        flag = 0
        # 탐색범위가 같아지거나 엇갈릴때까지 반복한다.
        while min_idx <= max_idx:
            # 중간지점의 위치를 구한다.
            avg_idx = (min_idx+max_idx)//2
            # 중간지점의 값이 정답이라면 answer를 늘리고 반복문을 중지한다.
            if A[avg_idx] == b:
                answer += 1
                break
            # 선택한 인덱스 값이 찾는값보다 크다면
            elif A[avg_idx] > b:
                # 선택한 인덱스 위쪽은 필요없으므로 최대 인덱스 위치를 수정한다.
                max_idx = avg_idx - 1
                # 이전에도 왼쪽을 선택했다면 중지
                if flag == 1: break
                # 왼쪽으로 갔다고 표시한다.
                flag = 1
            else:
                # 반대의 상황이라면 최소값을 바꿔준다.
                min_idx = avg_idx + 1
                # 이전에 오른쪽으로 갔다면 중지
                if flag == -1: break
                # 오른쪽으로 갔다고 표시한다.
                flag = -1
    print('#{} {}'.format(t+1, answer))