[BOJ][Python] 10816번 - 숫자카드2[정렬- 실버 4티어]

알고리즘 태그

[정렬]

태그 설명

정렬이란 데이터의 집합을 어떠한 기준의 대소관계를 따져 일정한 순서로 줄지어 세우는것

문제

백준 문제 - 숫자카드2

링크: 숫자카드2

문제설명

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

단순한 문제다. 말 그대로 상근이가 가지고 있는 카드가 정수에 있는지 없는지를 판단해서 결과값을 내어주면된다.

(이 전 글이 숫자카드1 이여서 쉽게 풀거같아서 도전했다...하지만..예상치 못한 복병이 있었다.)

이진탐색을 사용하여 도전을 진행하였다.

예제 입력 

10
6 3 2 10 10 10 -10 -10 7 3
8
10 9 -5 2 3 4 5 -10

예제 출력 

3 0 0 1 2 0 0 2

 

이진탐색이란?

데이터가 정렬되 있는 배열에서 특정한 값을 찾아내는 알고리즘이다. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다. X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

📃 소스코드 및 설명

# 상근이가 가지고 있는 카드수
# N = int(input())

# [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
N_list = list(map(int,input().split()))

# 정렬
# [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10]
N_list.sort()

# 주어지는 정수 갯수
M = int(input())

# [10, 9, -5, 2, 3, 4, 5, -10]
M_list = list(map(int,input().split()))

def binary_search(array, target, start, end):
  """  
  parameter
          array : 상근이가 가지고 있는 카드
          target : 주어진 정수에서 찾고자 하는 카드
          start : 0(리스트 인덱스)
          end : 상근이가 가지고 있는 카드의 길이의 끝점 인덱스   
  """
  # 시작포인트가 end보다 커지면 break
  # 즉 중간 지점을 기준으로 좌, 우로 움직이다 끝점이 start점보다 작아지는 경우 break을
  # 하게된다.
  while start <= end:
    # 두 숫자를 더해서 중간을 구하기 위해 몫을 구한다.
    mid = (start + end)//2
    if array[mid] == target:
      # 처음에 n - 1로 시작했기 때문에 전체 인덱스 갯수를 맞춰주기 위해서 end+1로 
      # 끝점을 추가해준다.
      return array[start:end+1].count(target)
    elif array[mid] > target:
      # 만약 중간값보다 배열의 값이 크다면 좌측으로 옮긴다.
      end = mid - 1
    else: 
      # array[mid] < target
      # 만약 중간값보다 배열의 값이 작다면 우측으로 옮긴다.
      start = mid + 1 
  return None
      
for i in range(M):
  # N_list의 요소들값을 기준으로해서 좌, 우로 움직여가며 탐색을 진행한다.
  # start, end는 아래와 같이 리스트의 처음부터 끝까지로 정해서 시작한다.
  result = binary_search(N_list, M_list[i], 0, N - 1)
  if result is not None:
    print(result, end=' ')
  else:
    print(0, end=' ')

숫자카드1과 다른점은 return만 다른줄 알았다! 때문에 기존에 이진탐색에서 유무를 파악하고 존재하는 위치부터 끝점까지를 count함수를 통해서 결과를 추출했지만,,,,,

 

런타임에러가 발생했다...

 

이 문제를 해결하기 위해 결국 다른사람의 답을 보기로 했다.

 

파이썬의 내장 모듈에는 이진 탐색을 해주는 모듈이 있었다.

bisect의 모듈을 사용해서 풀 수 있었다.

📃 소스코드 및 설명

"""
이진탐색으로 처리! 
* 리스트의 길이가 길어진다면 이진탐색을 통해서 하는게 효율적이다.
*******여기서는 bisect를 사용해서 풀었다는것이 포인트다!!*******
"""
from bisect import bisect_left, bisect_right
# 상근이가 가지고 있는 카드수
N = int(input())
# [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
N_list = list(map(int,input().split()))

# 정렬
# [-10, -10, 2, 3, 3, 6, 7, 10, 10, 10]
N_list.sort()

# 주어지는 정수 갯수
M = int(input())

# [10, 9, -5, 2, 3, 4, 5, -10]
M_list = list(map(int,input().split()))

def bisect_func(N_list, left_value, right_value):
    """  
    parameter
            array : 상근이가 가지고 있는 카드
            left_value : 찾고자하는 값
            right_value : 찾고자하는 값
    """
    # bisect_right : 이진탐색 탐색 모듈로서,
    # 내가 찾고자하는 값의 index + 1값을 반환한다.
    right_index = bisect_right(N_list, right_value)

    # 내가 찾고자하는 값의 index 값을 반환한다.
    left_index = bisect_left(N_list, left_value)

    # 결국 내가 찾고자하는 값의 index부터 index+1까지 찾게 되므로
    # 두 수를 빼면 갯수가 나오게된다
    # EX) 
    # [6, 3, 2, 10, 10, 10, -10, -10, 7, 3]
    # [10, 9, -5, 2, 3, 4, 5, -10]
    # left_index: 3
    # right_index : 6(10이 연속되므로 가장 마지막 index + 1을 반환한다.)
    return right_index - left_index

for i in range(M):
    print(bisect_func(N_list, M_list[i], M_list[i]), end=' ')