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

가독성을 위해서 문제 설명은 생략합니다. 링크를 통해 확인해 주세요.

 

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

프로그래머스

 

풀이 ✏️

using System;

public class Solution {
    public int solution(int n, long l, long r) 
    {
        int answer = 0;
        for(l--;l<r;l++)
        {
            checkCantor(l, ref answer);
        }
        return answer;
    }
    private void checkCantor(long l, ref int answer)
    {
        if(l < 5 && l != 2)
        {
            answer++;
        }
        else if(l%5 != 2)
        {
            checkCantor(l/5, ref answer);
        }
    }
}

 

풀이 방법 🤔

n이 1일 때, 유사 칸토어 비트열 "11011"

n이 2일 때, 유사 칸토어 비트열 "11011 11011 00000 11011 11011"

...

규칙성을 찾을 수 있다.

k번 째의 값은 k를 5로 나눈 몫에 해당하는 값이다.

k번 째의 값이 k를 5로 나눈 나머지가 2인 경우는 0이다.

 

k가 7인 경우 : 5로 나눈 나머지가 2 이기 때문에 0이다.

k가 8인 경우 : 5로 나눈 몫이 2가 아니기 때문에 1이다.

k가 13인 경우 : 5로 나눈 몫이 2이기 때문에 0이다.

 

문제 회고 🚦

시간초과를 어떻게 해결할 것인가?

 

처음에는 n의 값에 따라서 유사 칸토어 비트열을 생성했다.

해당 비트열을 순회하며, 범위 안 1의 개수를 체크했다.

결과는 시간초과였다. 아래는 '시간초과' 코드

using System;
using System.Linq;

public class Solution {
    public int solution(int n, long l, long r) 
    {
        string cantor = makeCantor(n,"1");
        var checkRange = cantor
            .Where((_,i)=>
                (l-1) <= i && i < r
            );
        int answer = checkRange.Count(c => c == '1');
        return answer;
    }
    private string makeCantor(int n, string s)
    {
        if(n <= 0)
        {
            return s;
        }
        string result = "";
        foreach(char c in s)
        {
            if(c == '1')
            {
                result += "11011";
            }
            else
            {
                result += "00000";
            }
        }
        return makeCantor(n-1, result);
    }
}

 

매번 유사 칸토어 비트열을 구하지 않고, 규칙성을 찾아서 해당 값을 찾아야 한다.

위 풀이방법에 따라 해당 문제를 해결할 수 있었다.

 

C#의 메서드는 기본적으로 Value로 매개 변수를 전달하기 때문에, 해당 변수의 메모리에 접근하지 않는다.

메모리에 접근하여 값을 수정하고 싶었기 때문에 ref 키워드를 사용했다.

변수를 매개 변수로 받지 않고 answer++;가 되는 순간마다 return 1; 을 하고, 이외의 경우 return 0;을 해도 될 것 같다.