문제 링크

개똥벌레

문제 설명

문제 풀이

시도 1

일단은 단순한 코드를 짰는데, python의 sum() 함수의 시간복잡도도 O(N)이라 시간초과가 났다 ^_^ ,,

import sys

input = sys.stdin.readline
N, H = map(int, input().split())
#구간 i에서
bottom = [0]*(H+1) #석순 -> 길이 i 이상면 부셔야함
top = [0]*(H+1) #종유석 -> 길이 N-i 이상이면 부셔야함
for _ in range(N//2):
    b = int(input().strip())
    bottom[b] += 1
    t = int(input().strip())
    top[t] += 1
min_val = [0]*N
answer = N
for i in range(1, H+1):
    b = sum(bottom[i:])
    t = sum(top[H-i+1:])
    answer = min(answer, b+t)
    min_val[b+t] += 1
print(answer, min_val[answer])

시도 2 - binary_search

모르겠어서 http://blog.naver.com/PostView.nhn?blogId=crm06217&logNo=222023706440&categoryNo=23&parentCategoryNo=0&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView를 참고했다. ^_ㅠ,,

이분탐색의 대상을 리스트에서 x보다 큰 값을 갖는 인덱스로 둬야 한다.

import sys

input = sys.stdin.readline
N, H = map(int, input().split())

bottom = [] #석순 -> 길이 i 이상면 부셔야함
top = [] #종유석 -> 길이 N-i 이상이면 부셔야함
for _ in range(N//2):
    bottom.append(int(input().strip()))
    top.append(int(input().strip()))
bottom.sort()
top.sort()

#lst에서 x보다 큰 데이터의 개수 구하기
def binary_search(lst, x):
    start, end = 0, len(lst)-1
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] <= x:
            start = mid + 1
        else:
            end = mid - 1
    return len(lst) - (end+1)

answer = N
count = 0
for i in range(1, H+1):
    tmp = binary_search(bottom, i-1) + binary_search(top, H-i)
    if tmp < answer:
        answer = tmp
        count = 1
    elif tmp == answer:
        count += 1

print(answer, count)