[백준] 19637번 파이썬 - 이분탐색, bisect

문제요약 (19637. IF문 좀 대신 써줘)

 

19637번: IF문 좀 대신 써줘

 

 

풀이를 위한 부연 설명

• 두 가지 방법으로 풀 수 있는 문제이기에 나눠서 작성하겠다.

 

이분탐색

• 각 칭호의 이름과 기준을 받아온다.
  • 이때 중복되지 않는 값을 받아오도록 처리를 해야한다.
• 이후 입력받은 캐릭터의 힘이 기준치 어디에 포함되는지 확인한다.
  • 인덱스 값을 기준으로 하여 이분탐색을 진행한다.

 

bisect 이용

• 훨씬 간결하고 빠른 코드이다.
• bisect
  • 이진 탐색을 쉽게 구현할 수 있는 라이브러리
  • 정리된 배열에서 사용 가능 (문제에서 비내림차순이라고 했으므로 사용 가능)
• bisect_left / bisect_right
  • 시간 복잡도 O(logN)
  • bisect_left(a, x) :정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
  • bisect_right(a, x) :정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
• 중복된 칭호가 들어올 수 있으므로 이번 문제에서는 bisect_left를 이용해야한다.
  • 동일한 value가 존재하면 가장 왼쪽 칭호를 반환하기 때문

 

• bisect 에 대한 자세한 개념 설명과 연관 문제는 다음 링크를 참고하면 된다.

 

[코테 알고리즘] 파이썬 기본 / 관련 문제

 

코드 

이분 탐색

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

titles = []
nums = []

for _ in range(n):
    a, b = input().split()
    if nums and nums[-1] == int(b):
        continue
    titles.append(a)
    nums.append(int(b))

for _ in range(m):
    character = int(input())

    start = 0
    end = len(titles) - 1

    while start <= end:
        mid = (start + end) // 2
        if character > nums[mid]:
            start = mid + 1
        else:
            end = mid - 1

    print(titles[end + 1])

 

 

bisect

import sys
input = sys.stdin.readline
from bisect import bisect_left

n, m = map(int, input().split())

titles = []
nums = []

for _ in range(n):
    a, b = input().split()
    titles.append(a)
    nums.append(int(b))

for _ in range(m):
    print(titles[bisect_left(nums, int(input()))])

 

 

기억할 점

• 이분탐색 문제라는 것을 알아야한다.
• 파이썬에는 이진 탐색을 쉽게하는 라이브러리 "bisect"가 있다.
• 같은 값이 있을 때 왼쪽을 확인해야하는지 오른쪽을 확인해야하는지 확인하기