[Silver III] 진수 정렬 (Easy) - 32283

문제 링크

성능 요약

메모리: 110576 KB, 시간: 100 ms

분류

브루트포스 알고리즘, 정렬

제출 일자

2026년 04월 25일 22:04:59

문제 설명

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

정렬 기준은 다음과 같다.

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

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

• 000
• 100
• 010
• 001
• 110
• 101
• 011
• 111

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

입력

첫째 줄에 이진수의 길이 $N$이 주어진다.

둘째 줄에 길이 $N$의 이진수 $S$가 주어진다.

이진수는 0으로 시작할 수 있다.

출력

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

위치는 $0$번부터 시작한다.

---

💡 해결 방법

💻 코드

# # 진수 정렬 (Easy)
 
# # 시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
# # 1 초	1024 MB	175	125	104	76.471%
# # 문제
# # 한별이는 길이 $N$의 이진수를 모두 모은 뒤 특별한 방식으로 정렬하여 사용하려 한다.
 
# # 정렬 기준은 다음과 같다.
 
# # 이진수 내의 1의 개수로 오름차순 정렬한다.
# # 1의 개수가 같다면 이진수를 뒤집었을 때의 오름차순으로 정렬한다.
# # 예를 들어, $N$이 3일 때 이진수는 다음 순서로 정렬된다.
 
# # 000
# # 100
# # 010
# # 001
# # 110
# # 101
# # 011
# # 111
# # 어느날 친구 선린이가 찾아와 길이가 $N$인 이진수 하나를 주며 몇 번째 위치에 있는지 알려달라고 했다. 하지만 한별이는 다른 일이 많아 아직 이진수들을 정렬하지 못했다. 한별이를 도와주자!
 
# # 입력
# # 첫째 줄에 이진수의 길이 $N$이 주어진다.
 
# # 둘째 줄에 길이 $N$의 이진수 $S$가 주어진다.
 
# # 이진수는 0으로 시작할 수 있다.
 
# # 출력
# # 주어진 이진수와 길이가 같은 모든 이진수를 정렬하였을 때, 주어진 이진수는 몇 번째 위치에 있는지 출력한다.
 
# # 위치는 $0$번부터 시작한다.
 
# # 제한
# #  $1\le N\le 10$ 
# # 예제 입력 1 
# # 5
# # 01101
# # 예제 출력 1 
# # 22
# https://www.acmicpc.net/problem/32283
 
 
import sys
 
input = sys.stdin.readline
 
n = int(input())
s = int(input(), 2)
 
 
 
 
 
 
list1 = []
 
for i in range(0, 2**n):
    list1.append(i)    
 
 
 
 
 
list1.sort(key = lambda x : (bin(x).count('1'),    bin(x)[::-1] ) )
 
 
list2 = [f'0b{i :0{n}b}' for i in list1]
 
#print(*list2, sep = '\n')
 
print(list1.index(s))