백준32283🐨진수 정렬 (Easy)-비트 연산

진수 정렬 (Easy)

한별이는 길이 N의 이진수를 모두 모은 뒤 특별한 방식으로 정렬하여 사용하려 한다.
정렬 기준은 다음과 같다:

1. 이진수 내의 1의 개수로 오름차순 정렬한다.
2. 1의 개수가 같다면 이진수를 뒤집었을 때의 오름차순으로 정렬한다.

예를 들어, N이 3일 때 이진수는 다음 순서로 정렬된다:

000
100
010
001
110
101
011
111

어느 날 친구 선린이가 찾아와 길이가 N인 이진수 하나를 주며 몇 번째 위치에 있는지 알려달라고 했다. 하지만 한별이는 다른 일이 많아 아직 이진수들을 정렬하지 못했다. 한별이를 도와주자!

입력

첫째 줄에 이진수의 길이 N이 주어진다.
둘째 줄에 길이 N의 이진수 S가 주어진다.
이진수는 0으로 시작할 수 있다.

출력

주어진 이진수와 길이가 같은 모든 이진수를 정렬하였을 때, 주어진 이진수는 몇 번째 위치에 있는지 출력한다.
위치는 0번부터 시작한다.

제한

제한 조건	1 ≤ N ≤ 10

예제 입력/출력

입력

5
01101

출력

22

 

def s():
    n,s=open(0).read().split()
    n=int(n)
    ref_rev=s[::-1]+'b0'
    ref_bit=ref_rev.count('1')
    c=0
    for i in range((1<<n)-1):
        rev=bin(i)[::-1]
        bit=rev.count('1')
        c+=(bit<ref_bit) or (bit==ref_bit and rev<ref_rev)
    print(c)
s()

 

n,s=open(0).read().split()
n=int(n)
ref_rev=s[::-1]+'b0'
ref_bit=ref_rev.count('1')
c=0
for i in range((((1<<ref_bit)-1)<<(n-ref_bit))+1):
    rev=bin(i)[::-1]
    bit=rev.count('1')
    c+=(bit<ref_bit) or (bit==ref_bit and rev<ref_rev)
print(c)

진수 정렬 (Hard)