멘탈이 엄청나간 문제..
그렇게 어렵진않은데 왜안되지 왜안되지 하다가
노트북을 반대로 접어버리고 싶은 마음이 굴뚝같았던 문제다.ㅠㅠ
의외로 과정은 간단한데
1. 정수를 2진수로 바꾼다.
2. 포화이진트리에 맞게 0을 추가해준다.
3. DFS 탐색으로 확인한다.
단계는 이렇게 3단계로 쉬우면서 아주 어려운 문제였다.
- 정수를 2진수로 바꾸기
for (int i = 0; i < numbers.size(); i++) {
long long n = numbers[i];
makebit(n);
}
void makebit(long long n) {
while (n != 1) {
if (n % 2 == 0) {
q.push_front(0);
}
else {
q.push_front(1);
}
n /= 2;
}
q.push_front(1);
changeToFullDec();
}그냥 우리 2진법 만드는것처럼 똑같이 계산해서 넣어주면된다.
2진법은 반드시마지막에 무조건 1이 남으니까 1을 넣어주면된다.
- 포화 이진트리만들기
일단 나는 여기서 반례를 찾았는데 그냥 2의 배수가 아니면 앞에다가 0을 하나 넣어줬는데 이러면 안되고
포화 이진트리는 층수를 n이라고 하면 2^n-1개의 노드가 있어야한다.
만약에 지금 11을 2진법으로 바꾸면 1011이고, 그 다음 2^2-1은 3이니까 2^3-1인 7개가 포화 이진트리의 갯수가 되고 즉 7-4인 3인 0을 3번 앞에다가 넣어줘야한다.
왜냐하면, 2진법으로 0을 앞에 넣어줘야 정수 11->1011 이 0001011과 동일하기 때문이다.
void changeToFullDec() {
int idx = 2;
while (true) {
if (q.size() <= idx - 1) break;
idx *= 2;
}
int s = idx - 1 - q.size();
for (int i = 0; i <= s; i++) q.push_front(0);
}- DFS확인하기
//애초에 rootnode가 0인경우
if (q[q.size() / 2] == 0) {
answer.push_back(0);
}
else {
int checksize = q.size() / 2;
if (checksize % 2 != 0) {
checksize++;
}
mycheck(q.size() / 2, 1, checksize/2);
if (tmp==0) {
answer.push_back(1);
}
else {
answer.push_back(0);
}
}처음에 if문은 애초에 rootnode가 0인경우이다. rootnode는 q에 들어가있는 size만큼의 딱 절반이므로 그 값을 확인하면 된다.
그다음에 이제 확인을 어떤식으로 해야하냐면, 0123456의 배열 index가 들어있으면,
우리의 rootnode는 3이었다. 그다음에 check를 1번과 5번을 해줘야하는데 이 숫자는 3에서 2를 빼거나 더해야한다.
그러므로 roonode가 홀수이면 +1을 해서 반으로 나눠준다.
만약 roodnode가 짝수라면 그냥 절반 나눈게 그 checksize가 된다.
그다음에 mycheck에다가 rootnode와 flag인 1 check해야할 size를 넣어주고 mycheck로 간다.
size와 flag가 이해안가도 일단 다음 함수를 보면서 확인하면 된다.
void mycheck(long long top, int flag, long long checksize) {
int a = q[top];
visited[top] = true;
if (flag == 0 && a == 1) {
tmp++;
return;
}
if (top - checksize >= 0 && top + checksize < q.size() && !visited[top - checksize] && !visited[top + checksize]) {
if (tmp == 0) {
mycheck(top - checksize, a, checksize / 2);
}
if (tmp == 0) {
mycheck(top + checksize, a, checksize / 2);
}
}
}자 일단 index가 0123456으로 있다고 치자, 그러면 top이3 그리고 flag가1 checksize가 2일 것이다.
그러면 방문처리를 해준다.
그리고 if문을 보는데 부모가 0인데 자식이 1인 경우를 tmp++하고 return해준다.
그게 아니라면 top+checksize인 5번과 top-checksize인 1번을 범위를 넘는지 방문을 이미 했는지 확인하고 넘어간다.
그리고tmp가 0이어야 mycheck재귀함수로 부르면서 확인한다.
만약 왼쪽을 전부 확인했는데 부모가 0인데 자식이 1인게 있으면 tmp가 1이되고, 그다음에 tmp가 전역변수니까 나머지 if문을 모두 수행하지 않는다.
전체코드
#include <string>
#include <vector>
#include <iostream>
#include <deque>
#include <cstring>
using namespace std;
deque<int>q;
bool visited[100] = { false, };
int tmp = 0;
void changeToFullDec() {
int idx = 2;
while (true) {
if (q.size() <= idx - 1) break;
idx *= 2;
}
int s = idx - 1 - q.size();
for (int i = 0; i <= s; i++) q.push_front(0);
}
void makebit(long long n) {
while (n != 1) {
if (n % 2 == 0) {
q.push_front(0);
}
else {
q.push_front(1);
}
n /= 2;
}
q.push_front(1);
changeToFullDec();
}
void mycheck(long long top, int flag, long long checksize) {
int a = q[top];
visited[top] = true;
if (flag == 0 && a == 1) {
tmp++;
return;
}
if (top - checksize >= 0 && top + checksize < q.size() && !visited[top - checksize] && !visited[top + checksize]) {
if (tmp == 0) {
mycheck(top - checksize, a, checksize / 2);
}
if (tmp == 0) {
mycheck(top + checksize, a, checksize / 2);
}
}
}
vector<int> solution(vector<long long> numbers) {
vector<int> answer;
for (int i = 0; i < numbers.size(); i++) {
long long n = numbers[i];
makebit(n);
//애초에 rootnode가 0인경우
if (q[q.size() / 2] == 0) {
answer.push_back(0);
}
else {
int checksize = q.size() / 2;
if (checksize % 2 != 0) {
checksize++;
}
mycheck(q.size() / 2, 1, checksize/2);
if (tmp==0) {
answer.push_back(1);
}
else {
answer.push_back(0);
}
}
//작업처리후 vclear
q.clear();
tmp = 0;
for(int i=0;i<100;i++){
visited[i]=false;
}
}
return answer;
}