[프로그래머스 C++] 유사 칸토어

[프로그래머스 C++] 유사 칸토어

 

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

프로그래머스

---

 

해결전략

 

수학

재귀

---

 

처음 시도한 코드 - 시간초과

 

#include <string>
using namespace std;

int solution(int n, long long l, long long r) {

    string str = "1";
    while (n--) 
    {
        string temp = "";
        for (int i = 0; i < str.size(); i++) {
            if (str[i] == '0') {
                temp += "00000";
            }
            else if (str[i] == '1') {
                temp += "11011";
            }
        }
        str = temp;
    }

    int answer = 0;
    for (int i = l-1; i < r; i++) {
        if (str[i] == '1') {
            answer++;
        }
    }

    return answer;
}

 

#include <string>
#include <vector>
using namespace std;

int solution(int n, long long l, long long r) {

    string str = "1";
    string zero = "0";
    while (n--) 
    {
        string temp = str + str + zero + str + str;
        str = temp;
        string temp_zero = zero + zero + zero + zero + zero;
        zero = temp_zero;
    }

    int answer = 0;
    for (int i = l-1; i < r; i++) {
        if (str[i] == '1') {
            answer++;
        }
    }

    return answer;
}

 

---

 

정답코드

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool CheckOne(long long x) // 주어진 인덱스에 해당하는 문자가 '1'인지 확인하는 함수
{
    // 5보다 작은 경우, 2를 제외하고는 모두 '1'에 해당
    if (x < 5 && x != 2) return true;

    // 5로 나누어 떨어지는 경우는 '0'에 해당
    if ((x - 2) % 5 == 0) return false;

    // 위의 경우에 해당하지 않으면, x를 5로 나눈 몫에 대해 재귀 호출
    return CheckOne(x / 5);
}

long long solution(int n, long long l, long long r) {
    
    int answer = 0;

    for (long long i = l-1; i < r; i++) { // l부터 r까지 각 인덱스에 대해 '1'인지 확인
        if (CheckOne(i)) answer++; // '1'이면 answer 증가
    }

    return answer;
}

int main() {
    cout << solution(2, 4, 17) << "\n"; // 8
    cout << solution(4, 30, 118) << "\n"; // 39
    cout << solution(3, 1, 125) << "\n"; // 64
    cout << solution(4, 27, 68) << "\n"; // 15

    return 0;
}

 

 

인덱스 i가 '1'에 해당하는지 확인하는 CheckOne 함수를 사용하여 특정 범위 l부터 r까지의 '1'의 개수를 센다.

• CheckOne 함수는 인덱스 i가 5로 나누어 떨어지는 경우 '0'에 해당하고,
• 그렇지 않으면 i를 5로 나눈 몫에 대해 재귀적으로 '1'인지 확인

위의 방법으로 '1'의 개수를 센다. 시간 복잡도는 O(N log N)

 

 

 

(x - 2) % 5 == 0 이면 false인 이유는?

 

 '11011' 패턴에서 '0'은 3번째 위치에 있다.

그런데 배열의 인덱스는 0부터 시작하기 때문에, 우리가 체크하려는 인덱스에서 2를 빼주어야 실제로 5개의 블록을 이루는 패턴에서 '0'이 위치하는 인덱스를 찾을 수 있다. 즉, (x-2)%5가 0이라는 것은 x번째 위치의 숫자가 '0'이라는 뜻이다. 따라서 이 경우에는 false를 반환하고, 그 외의 경우에는 true를 반환한다.

이렇게 (x-2)%5를 이용하여 주어진 인덱스에 해당하는 문자가 '1'인지 '0'인지를 판단한다. 

---

 

 

다른 방식의 풀이

 

https://allmymight.tistory.com/188

 

https://velog.io/@aoleejohn/C-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%9C%A0%EC%82%AC-%EC%B9%B8%ED%86%A0%EC%96%B4-%EB%B9%84%ED%8A%B8%EC%97%B4