[프로그래머스] 유사 칸토어 비트열 C++
in Study on Coding Test
규칙성을 찾는 문제
정답 참고 링크
정답제출코드
#include <string>
#include <cmath>
using namespace std;
int count_bit(long long num)
{
if (num <= 5)
{
int count = 0;
string s = "11011";
for (int i = 0; i < num; ++i)
{
if (s[i] == '1')
count++;
}
return count;
}
int base = 1;
while (pow(5,base+1) < num)
base++;
int section = num / (pow(5, base));
int remainder = num % (int)(pow(5, base));
int to_return = section * (pow(4, base));
if (section >= 3)
to_return -= pow(4, base);
if (section == 2)
return to_return;
else
return to_return + count_bit(remainder);
}
int solution(int n, long long l, long long r) {
int answer = count_bit(r) - count_bit(l - 1);
return answer;
}
오답제출코드1 (시간초과)
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
queue<int> canto(queue<int> a, int b, int n)
{
if (b == n)
return a;
queue<int> new_a;
while(!a.empty())
{
int k = a.front();
if (k == 0)
{
for (int i = 0; i < 5; ++i)
new_a.push(0);
}
else if (k == 1)
{
new_a.push(1);
new_a.push(1);
new_a.push(0);
new_a.push(1);
new_a.push(1);
}
a.pop();
}
queue<int> to_return = canto(new_a, b+1, n);
return to_return;
}
int solution(int n, long long l, long long r) {
queue<int> a;
a.push(1);
queue<int> for_ans = canto(a, 0, n);
int answer = 0;
long long counter = 1;
while (!for_ans.empty())
{
if (l <= counter && counter <= r)
{
int k = for_ans.front();
if (k == 1)
answer++;
}
for_ans.pop();
counter++;
}
return answer;
}
기존 큐의 숫자를 뽑아서 1이면 새로운 큐에 11011을, 0이면 00000을 넣는 방식으로 구현하였다.
이를 재귀함수를 통해서 반복하도록 하였다.
하지만 시간초과라는 결과를 낳았다. 뭐가 문제였을까?
오답제출코드2 (시간초과)
#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
string canto(string a, int b, int n)
{
if (b == n)
return a;
string new_a;
int len = a.length();
int counter = 0;
while(counter < len)
{
char k = a[counter];
if (k == '0')
{
new_a += "00000";
}
else if (k == '1')
{
new_a += "11011";
}
counter++;
}
string to_return = canto(new_a, b+1, n);
return to_return;
}
int solution(int n, long long l, long long r) {
string a;
a = "1";
string for_ans = canto(a, 0, n);
int answer = 0;
for (long long i = l; i <= r; ++i)
{
if (for_ans[i-1] == '1')
answer++;
}
return answer;
}
같은 로직을 string을 이용해서 풀어보았다. 하지만 역시 결과는 같았다.
방향이 잘못된 것일까?
재귀함수 자체를 쓰면 안되는 것일까? 생각을 해본다.
오답제출코드3 (시간초과)
#include <string>
#include <queue>
#include <iostream>
using namespace std;
int solution(int n, long long l, long long r) {
queue<int> a;
a.push(1);
int counter = 0;
while(counter < n)
{
queue<int> new_a;
while(!a.empty())
{
int k = a.front();
if (k == 0)
{
for (int i = 0; i < 5; ++i)
new_a.push(0);
}
else if (k == 1)
{
new_a.push(1);
new_a.push(1);
new_a.push(0);
new_a.push(1);
new_a.push(1);
}
a.pop();
}
a = new_a;
counter++;
}
int answer = 0;
long long index = 1;
while (!a.empty())
{
if (l <= index && index <= r)
{
int k = a.front();
if (k == 1)
answer++;
}
a.pop();
index++;
}
return answer;
}
재귀함수를 쓰지 않고 while문으로 해보았다.
그러나 재귀함수를 쓸 때 보다 오히려 더 시간이 소요된 것 같다.
오답제출코드4 (시간초과)
#include <string>
#include <iostream>
using namespace std;
int solution(int n, long long l, long long r) {
string a;
a = "1";
int counter = 0;
while(counter < n)
{
string new_a;
int len = a.length();
for (int i = 0; i < len; ++i)
{
char k = a[i];
if (k == '0')
{
new_a += "00000";
}
else if (k == '1')
{
new_a += "11011";
}
}
a = new_a;
counter++;
}
int answer = 0;
for (long long i = l; i <= r; ++i)
{
if (a[i-1] == '1')
answer++;
}
return answer;
}
헤헤 역시 시간초과다.
다만, 큐를 쓸 때보다는 시간이 덜 걸린 것 같다.
이쯤되면 로직이 잘못된 것일까?
수학적인 규칙을 찾아야 하나 생각이 든다.
생각해보니 5등분을 하고난 다음에 3번째 조각은 모두 0이니 그것을 날려버릴 수 있다.
정답코드로의 변환
몇 시간이 지나도 정답을 찾는 방법이 떠오르지 않아서 결국 검색을 했다.
해당 링크에 있는 코드를 참고하였다.
파이썬으로 되어있는 것을 해석해보니 대략 l번째 까지 있는 1의 개수에서 r번째 까지 있는 1의 개수를 빼는 구조이다.
비트열의 길이가 5의 n승인 것을 이용하면 된다.
