23.02.15 파이썬 코딩 퀴즈#157 유사 칸토어 비트열 (프로그래머스 스쿨)

이번 문제는 유사 칸토어 비트열 문제이다.

어제부터 굉장히 고민을 하게 만든 문제인데, 오늘 tstory 들어왔더니 어제 작성했던 글이 다 날아갔다...

먼저 문제에서 설명하는 칸토어 비트열이란 비트열의 1은 11011 로, 0 은 00000 으로 치환하여 만드는 비트열이다.

그림으로 표현하면 대충 이런 느낌이고, 가운데 계속 생겨나는 공란이 바로 0이 된다.

대충 표현하자면 이런 느낌이랄까?

구해야 하는건 폐구간 [l,r] 에 존재하는 1의 개수를 구해야 한다.

어제 작성해둔 코드는 이미 날아갔기 때문에 다시 볼 순 없고, 이 문제를 비트열을 만들어 풀려고 하면 당연히 시간 초과에 걸린다.

일단 비트열의 생성 규칙에서 알 수 있는 정보는

1. n=1 을 제외한 비트열을 5로 나누게 되면 가운데 값(index 2)는 0 또는 0으로 가득차 있다.

2. 이 때 구역마다 1의 개수는 4개이다.

3. 즉 [1 4개][1 4개][0][1 4개][1 4개] 의 일정한 배열을 가지게 되며 최종적으로 비트열이 가지는 1의 개수는 4**n 이다.

문제에 접근하는 방법은 여러가지가 있다.

해당 구역을 "11011"이 되는 가장 작은 구역으로 나누어 l, r 의 위치를 확인하고 값을 찾거나,

또는 구역의 0의 값을 찾아서 폐구간의 길이에서 빼주는 방법이 있다.

내가 선택한 방법은 폐구간의 길이에서 0을 찾아 빼주는 방법이다.

코드에 크게 설명이 필요한 부분이 저 while 문 인것 같은데, 입출력 예의 값을 집어넣어 확인해보자.

n, l, r = 2, 4, 17

먼저 answer 에는 r-1+1 즉 해당 구간의 요소들의 개수가 저장이 된다. 이 때 저장되는 값은 14이다.

이제 범위를 탐색하며 해당 위치의 값을 확인하게 되는데, 7 인 경우를 살펴보자.

7 을 몫과 나머지로 분리하면 1,2 가 된다. 여기서 index 2는 0을 의미한다. 따라서 answer 의 값을 1 감소 시켜준다. 그리고 break 를 만나 종료된다.

8 을 몫과 나머지로 분리하면 1,3 이 된다. 그리고 다시 num = 1 이 되지만, while문 조건에 맞지 않아 종료된다.

11의 경우에도 (2,1) 이 나오는데 a 값이 2 인 경우에는 그 구역 전체가 0으로 가득차 있다. 따라서 answer의 값을 1 감소 시켜준다. break 를 만나 종료된다.

 

n=3 인 경우 그 길이는 125가 되는데, 이때 0의 index를 위 코드를 활용하여 (a,b)로 나타내면

(0,2)(1,2)(2,0~4),(3,2),(4,2)(5,2)(6,2)(7,0~4) .... 으로 나타내 지며 마지막 0의 좌표는 (24,2)가 된다. 

(7,0)을 돈다고 가정하면 num = 7 이 되어 다시 while문을 돌게되고, 이 때 좌표는 다시 (1,2)로 갱신된다. 따라서 0 좌표 이므로 answer 값을 1 감소 시키고 종료된다.