[python code review] 5주차 (숫자카드2, K번째 수, 균형점)

https://www.acmicpc.net/problem/10816

10816번: 숫자 카드 2

[dictionary, 이진탐색 사용]

이미 카운트했던 카드를 처리해주지 않아서 처음에 시간 초과가 발생했었다. 

n = int(input())
cards = sorted((map(int, input().split())))
m = int(input())
targets = list(map(int, input().split()))
result = []

# 처음에 등장하는 원소의 인덱스 값을 구하는 함수
def findLeftIdx(target):
    start, end = 0, n-1
    while start <= end:
        mid = (start + end)//2
        if cards[mid] < target:
            start = mid + 1
        elif cards[mid] > target:
            end = mid - 1
        elif cards[mid] == target and (mid == 0 or cards[mid-1] < cards[mid]):
            return mid
        else:
            end -= 1
    return -1

# 원소가 존재하는 경우 findLeftIdx에서 구한 인덱스부터 +1씩 접근하여 개수 카운트
def count(target):
    cnt = 0
    for i in range(left, n):
        if cards[i] == target:
            cnt += 1
        else:
            break
    return cnt

dic = {}
for t in targets:
    # 이미 카운트했던 카드인 경우
    if dic.get(t, 0):
        result.append(dic[t])
        continue
    left = findLeftIdx(t)
    # 원소를 발견하지 못한 경우
    if left == -1:
        result.append(0)
        dic[t] = 0
        continue
    else:
        c = count(t)
        result.append(c)
        dic[t] = c
print(*result)

아래와 같이 함수 최적화 가능

def findLeftIdx(target):
    start, end = 0, n-1
    while start <= end:
        mid = (start + end)//2
        if cards[mid] == target and (mid == 0 or cards[mid-1] < cards[mid]):
            return mid
        elif cards[mid] >= target:
            end = mid - 1
        else:
            start = mid + 1
    return -1

 

[bisect 사용]

bisect 라이브러리를 사용하여 매우 간단하게 풀이할 수 있었다. 이 경우, 이미 카운트한 카드의 정보를 dic 딕셔너리를 통해 관리하지 않아도 시간초과가 발생하지 않았다!

import bisect

n = int(input())
cards = sorted(map(int, input().split()))
m = int(input())
targets = list(map(int, input().split()))

def count(arr, target):
    a = bisect.bisect_left(arr, target)
    b = bisect.bisect_right(arr, target)
    return b-a

result = []
for t in targets:
    result.append(count(cards, t))
print(*result)

 

https://www.acmicpc.net/problem/1300

1300번: K번째 수

n = int(input())
k = int(input())

def binarySearch(start, end):
    result = 0
    while start <= end:
        mid = (start + end)//2
        count = 0
        for i in range(1, n+1):
            count += min(mid//i, n)
        if count < k:
            start = mid + 1
        else:
            result = mid
            end = mid - 1         
    return result


print(binarySearch(0, n*n))

너무 어려워서 블로그를 참고했다. 사실 아직까지도 왜 마지막 else문의 mid 값이 B[k]가 되는지 잘 이해가지 않는다.

B[k] <= k라는 조건 때문에 end = k로 설정할 수 있음 

print(binarySearch(0, k))

 

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWG8amS6AkkDFAWc&lectureSeq=11&contestProbId=AV15MeBKAOgCFAYD&kataId=&&&&&&&&&& 

SW Expert Academy

def binarySearch(idx, start, end):
    mid = 0
    while (end - start) >= 1/(10**12):
        mid = (start + end) / 2
        left, right = 0, 0
        for k in range(n):
            force = m[k] / (mid-x[k])**2
            # 왼쪽에서 잡아당기는 인력인 경우
            if x[k] < mid:
                left += force
            else:
                right += force
        # 왼쪽에서 잡아당기는 인력이 더 크면
        if left > right:
            start = mid
        # 오른쪽에서 잡아당기는 인력이 더 크면
        else:
            end = mid
    return mid

for tc in range(1, int(input())+1):
    n = int(input())
    data = list(map(int, input().split()))
    x = data[:n]
    m = data[n:]
    # 좌표 xi와 xi+1 사이의 균형점 찾기(이분탐색)
    for i in range(0, n-1):
        result = binarySearch(i, x[i], x[i+1])
        print(f'#{tc} {result:.10f}')

블로그를 참고해도 어렵게 다가와서 미루고 미뤘던 문제.. 이런 문제를 보면 참 겸손해진다. 

문제 해설)

아래 그림처럼 각 점과 점 사이에 존재하는 균형점을 이진탐색을 통해 구하는 문제이다. 

i번째와 i+1번째 점 사이의 균형점을 구한다고 했을 때 start = xi, end = xi+1이다. 만약 왼쪽에서 작용하는 인력이 크다면 균형점은 좀더 오른쪽에 위치해야 한다. 따라서 시작점(start)인 xi을 현재 탐색 중인 mid 값으로 바꿔준다. 반대로 오른쪽에서 작용하는 인력이 크다면 균형점은 왼쪽에 위치해야 하므로 끝점인 xi+1을 mid 값으로 바꿔준다. 

문제에서 좌표값의 오차가 10 -12(1e-12) 보다는 작아야 한다고 했기에 두 좌표의 오차가 10 -12보다 작아질 때 mid 값을 균형점으로 return 해주면 정답이 된다. 

 

이 문제는 파라매트릭 서치 유형의 문제이기도 하다. dfs 문제에서 가지치기를 진행하는 경우(해가 아닐 경우 되돌아 가도록 구현) 백트래킹이라고 부르듯이 이 문제도 이진탐색을 사용하는 파라매트릭 서치 유형인가보다.

파라매트릭 서치에 대해서는 아래 블로그를 참고하면 쉽게 이해할 수 있다.  

https://velog.io/@lake/%EC%9D%B4%EB%B6%84%ED%83%90%EC%83%89-%ED%8C%8C%EB%9D%BC%EB%A9%94%ED%8A%B8%EB%A6%AD-%EC%84%9C%EC%B9%98Parametric-Search

[이분탐색] 파라메트릭 서치(Parametric Search)

 

어떤 최솟값과 최댓값 사이에 있는 target을 탐색할 경우, 선형탐색은 O(N)이지만 이진 탐색을 사용하면 O(logN)만에 탐색이 가능하다. 이게 이진탐색을 사용하는 근본적인 이유인데

월요일에 다룬 나무자르기 문제를 포함한 위 세 문제의 공통점은 10^7 ~ 10^9 사이의 큰 숫자를 input 값의 범위로 주었다는 것이다. 코딩테스트를 문제를 풀 때 input 값 범위를 크고 너무 크다 싶으면 이진탐색을 떠올려보는 게 좋은 방법인 듯 싶다.