[프로그래머스 C#] Lv.2 유사 칸토어 비트열

https://school.programmers.co.kr/learn/courses/30/lessons/148652

프로그래머스

1. 정답코드 및 핵심 아이디어, 유의사항

유사 칸토어 비트열의 일정 폐구간 안의 1의 개수를 구하는 문제

- 0번째 유사 칸토어 비트열은 "1"로 시작함

- 유사 칸토어 비트열은 아래와 같은 변환 과정을 거침

"1" -> "11011"

"0" -> "00000"

ex) 2번째 유사 칸토어 비트열 : "1101111011000001101111011"

 

풀이 핵심 ( n번째 유사 칸토어 비트열의 인덱스를 기준으로 함 )

1. 11011 형태에서 0 자리에 있는 경우

- 5로 나눈 나머지 값이 2인 경우 -> 무조건 0이 됨

2. 11011 형태에서 1 자리에 있는 경우 11011의 0에서 파생됐는지 여부를 판단하기 위해 1번째 유사 칸토어 비트열까지 거슬러 올라가서 판단해야 함

- 5로 나눈 값에 대해 5보다 작아질 때까지 1번 연산을 반복하며 체크

 

주석 참조

- 시간복잡도가 아슬아슬하게 통과되는 코드

    using System;

    public class Solution
    {
        public int solution(int n, long l, long r)
        {
            int answer = 0;
            
            // 조건의 폐구간의 모든 부분을 순회
            for (l = l - 1; l < r; l++)
                if (Function(l))
                    answer++;

            return answer;
        }

        // 유사 칸토어 비트열이 1이면 true를 반환하는 메서드
        public bool Function(long num)
        {
            if (num % 5 == 2) // "11011" -> "0"
                return false;
            else if (num < 5) // "11011" -> "1"
                return true;
            
            // 현재 유사 칸토어 비트열의 레벨에선 0이라고 확신할 수 없을 경우
            return Function(num / 5);
        }
    }