이 문제는 2023 KAKAO BLIND RECRUITMENT 4번째 문제이다.
https://school.programmers.co.kr/learn/courses/30/lessons/150367
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
이게 기억나는게 알고리즘 공부하면서 처음 본 코테였다. 내 기억으로 2022년 9월말인가? 봤었는데 광탈하고
지금에서야 다시 문제를 봤는데 조금 생각이 나면서도 새롭네 ㅎ
그때도 문제를 정확히 이해못했는데 지금은 놀랍게도 여전히 이해가 안갔다.
포화 이진트리가 뭔지도 헷갈려서 ㅎㅎ;
주어진 테스트 케이스를 모두 그리고 뚫어지게 쳐다보니 그때서야 이해가 갔다.
역시 노가다가 최고여
예제를 바꿔보면 이렇게 됐고,
되는 것과 안되는 것에 차이는 루트 노드부터 맨 아래 리프노드까지 붕뜨는 노드가 없어야한다는 것이었다.
쉽게 말해 부모 노드가 0인데 자식 노드가 1인 경우가 없어야한다.
이걸 판별하기 위해서는 모든 노드를 봐야해서
문자열을 반씩 잘라가면서 진행하고 결과를 다시 합치는 분할정복으로 구현했다.
쨋든 알고리즘을 시작하기 전에 선행되야할 것이 하나 있었는데
제시된 숫자를 이진법으로 바꾸는 것이었다.
위의 예제처럼 7 -> 111, 42 -> 101010 등으로 바꾼다음에 판별하는 것이다.
여러 방법이 있겠지만 심플하게 생각난 2를 나누고 난 나머지로 2진법 문자열을 만들었다.
요거 ㅋ
string to_2(long long num){
string str;
while(num/2!=0){
str.insert(0, to_string(num%2) );
num/=2;
}
str.insert(0, to_string(num));
return str;
}
코드로 하면 이렇게 된다.
근데 여기서! 예제와 차이점을 알아채야 한다.
보면 맨 위 그림에서는 42가 0101010으로 맨 앞에 0이 하나 더 붙어있다.
그렇다. 문제 조건이 포화 이진트리이기 때문에 문자열의 길이는 무조건 1(2¹-1), 3(2²-1), 7(2³-1) ... 으로 가야한다.
따라서 이 길이가 안된다면 추가로 부족한만큼 앞에 0을 붙여주는 작업을 해야한다.
이것을 코드로 하면 이렇게 된다.
string to_2(long long num){
string str;
while(num/2!=0){
str.insert(0, to_string(num%2) );
num/=2;
}
str.insert(0, to_string(num));
//////////////////////////////////////////부족한 만큼 앞에 0을 추가
if( log2(str.size()+1)!=(int) log2(str.size()+1) ){
int n = pow(2, ((int)log2(str.size()+1)) + 1) - 1;
n-=str.size();
for(int i=0; i<n; i++){
str.insert(0, "0");
}
}
///////////////////////////////////////
return str;
}이게 추가한 것인데... 약간 아리송하지만 당장 떠오르는 방법이라 이렇게 구현했다.
1, 3, 7... 은 2ⁿ-1꼴이기 때문에 2진법으로 만든 문자열의 길이에 +1을 하고 log2를 취하면 정수가 나와야한다.
if문에서 이것을 판별하고 n.xxxx꼴이 나온다면 n+1이 될때까지 앞에 0을 붙여줬다.
자, 이렇게 하고 나서야 본격적인 알고리즘에 들어갈 수 있다.
알고리즘은 위에서 말한대로 분할정복(divde-conquer: dq)방식으로 하며
자식 노드가 1인데 부모 노드가 0일 경우 -1을 return하고, 정상이면 부모 노드를 return한다.
아래서 한번이라도 -1이 나왔으면 쭉끌고 위로 올라와서 -1을 return 한다.
그림으로 하면 대충..뭐,, 이렇게
int dq(string str){
if(str.size()==1) return str[0] - '0';//1
long long half = str.size()/2;
int left = dq(str.substr(0, half));//2-1
int right = dq(str.substr(half+1));//2-2
if(left==-1 || right==-1) return -1;//3
if(str[half]=='0' && left+right!=0 ) return -1;//4
return str[half]- '0';//5
}//1: 리프 노드면 해당 리프노드를 반환
//2-1: 왼쪽으로 분할
//2-2: 오른쪽으로 분할
//3: 어느 한쪽에서 -1이 나왔으면 -1을 return;
//4: 부모 노드가 0인데 자식노드가 0이 아닐 경우 -1을 return;
//5: 정상적일땐 부모노드의 숫자를 return;
요롷게 해서 숫자마다 -1이 나오면 answer벡터에 0을 추가하고
-1이 아닐 경우 1을 추가하면 된다.
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
string to_2(long long num){
string str;
while(num/2!=0){
str.insert(0, to_string(num%2) );
num/=2;
}
str.insert(0, to_string(num));
if( log2(str.size()+1)!=(int) log2(str.size()+1) ){
int n = pow(2, ((int)log2(str.size()+1)) + 1) - 1;
n-=str.size();
for(int i=0; i<n; i++){
str.insert(0, "0");
}
}
return str;
}
int dq(string str){
if(str.size()==1) return str[0] - '0';
long long half = str.size()/2;
int left = dq(str.substr(0, half));
int right = dq(str.substr(half+1));
if(left==-1 || right==-1) return -1;
if(str[half]=='0' && left+right!=0 ) return -1;
return str[half]- '0';
}
vector<int> solution(vector<long long> numbers) {
vector<int> answer;
for(int i=0; i<numbers.size(); i++){
string s = to_2(numbers[i]);
if(dq(s)==-1) answer.push_back(0);
else answer.push_back(1);
}
return answer;
}이렇게 해서 풀코드가 나온다...
이 문제를 푼 소감이라면 사실 설명에 나온대로 순탄하게 풀지 못했다. 예제를 보고 이걸 알아채는 자체도 늦었고, 중간에 return 값을 부모노드가 아니라 자식노드로 해서 정답률이 25퍼밖에 안나오기도 했다. 그런데 이런 문제를 포함해서 적어도 1, 2, 3, 4번 문제는 제한시간안에 다 풀어야 통과라.. 허허 갑자기 자존감이 많이 하락하지만 뭐.. 그래도 저번엔 못풀었는데 이번엔 풀었잖아? ㅎ 이게 어디야 ~
개선점
문자열을 자르지말고 start, end 인덱스 인자를 넘겨서 인덱스로 했다면 시간이 좀더 줄까? 라는 생각을 했지만 문제를 맞췄단 기쁨에 그냥 생각만 하고 넘어갔다. 차이점은 substr을 안쓴다는 점인데, 이게 시간에 얼마나 차이를 줄지는 모르겠다. 사실 시간보단 공간이 줄거같긴하다. 끗