[BOJ] 23758 - 중앙값 제거 (Python)

 

 

아이디어

 

0이 등장하려면 중앙값 이하의 수가 모두 1이 되어야 한다.

 

 

풀이 #1

 

2의 거듭제곱마다 연산 횟수가 늘어나므로 2를 거듭제곱하며 중앙값 이하의 수에 대해 연산 횟수를 더해 나간다.

res는 중앙값 이하의 수가 모두 1이 되는 연산 횟수이므로 0이 등장하는 res+1을 출력한다.

 

def solution():
    N = int(input())
    A = sorted(map(int, input().split()))
    res = cnt = 0
    k = 2
    for i in range((N+1)//2):
        while k-1 < A[i]:
            cnt += 1
            k *= 2
        res += cnt
    print(res+1)

solution()

 

 

 

풀이 #2

 

연산 횟수는 2진수(비트)로 나타낸 수의 길이-1로 나타낼 수 있고, 비트 길이는 bit_length() 메서드로 구할 수 있다.

 

정렬을 빠르게 하기 위해 입력 받는 수를 모두 비트 길이로 바꿔 정렬한 다음 중앙값까지의 합+1을 출력한다.

 

def solution():
    N = int(input())
    A = sorted(map(lambda x: x.bit_length()-1, map(int, input().split())))
    print(sum(A[:(N+1)//2])+1)

solution()