진수 정렬 (Easy)
면접 대비시간 제한1초메모리 제한1024 MB
길이 N인 이진 문자열 S가 주어집니다. 길이 N의 모든 이진 문자열을 1의 개수와 뒤집은 문자열 순으로 정렬했을 때 S의 위치를 0부터 셉니다.
문제
한별이는 길이가 인 이진수를 모두 모은 뒤, 특별한 방식으로 정렬해서 사용하려 한다. 정렬 기준은 다음과 같다.
- 이진수 내의 1의 개수가 적은 순서로 오름차순 정렬한다.
- 1의 개수가 같다면, 이진수를 뒤집었을 때의 오름차순으로 정렬한다.
예를 들어, 이 3일 때 이진수는 다음 순서로 정렬된다.
- 000
- 100
- 010
- 001
- 110
- 101
- 011
- 111
어느 날 친구 선린이가 찾아와 길이가 인 이진수 하나를 주며 몇 번째 위치에 있는지 알려달라고 했다. 하지만 한별이는 다른 일이 많아 아직 이진수들을 정렬하지 못했다. 한별이를 도와주자!
입력
첫째 줄에 이진수의 길이 이 주어진다.
둘째 줄에 길이 의 이진수 가 주어진다.
이진수는 0으로 시작할 수 있다.
출력
주어진 이진수와 길이가 같은 모든 이진수를 정렬했을 때, 주어진 이진수가 몇 번째 위치에 있는지 출력한다.
위치는 0번부터 시작한다.