프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
- 문제 설명
본 문제는 입력값으로 주어진 10진수의 값이 주어진 조건에 의해 이진법 형태로 변경 후 이진트리의 형태로 구현될 수 있는가를 묻는 문제이다. 주어진 예시를 다시 한 번 살펴보면 다음과 같다.
예시
1) [7,42,5]
7은 이진법으로 111로 나타낼 수 있다. 이것을 완전이진트리로 나타내면 아래와 같이 간단하게 표현할 수 있다.
42는 이진법으로 101010 로 나타낼 수 있다. 이것을 완전이진트리로 표현하기 위해 앞에 '0'을 추가해, 0101010 으로 나타내면, 아래와 같이 표현할 수 있다.
5는 101이 되며, 완전이진트리로 표현할 수 없다.
2) [63,111,95]
63은 이진법으로 111111이며 완전이진트리로 표현하기 위해 0111111 로 변경하면, 아래와 같이 표현할 수 있다.
111은 이진법으로 1101111이며 바로 완전이진트리로 표현이 가능하다.
95는 이진법으로 1011111이며, 이는 완전이진트리로 표현할 수 없다.
- 문제 풀이
문제를 풀기위한 순서는 아래와 같다.
[1] 주어진 10진수를 이진수 문자열 형태로 변경
[2] 완전이진트리로 표현하기에 길이가 부족하다면, 더미값('0')을 넣어 완전이진트리로 표현할 수 있게 길이 조정
[3] 완전이진트리로 구현이 가능한지 확인
그렇다면, 1번부터 차근차근 알아보도록 하자.
[1] 주어진 10진수를 이진수 문자열 형태로 변경
우선 이진트리의 형태로 나타내기 위해, 주어진 10진수를 이진수로 변경해야 한다. 10진수를 이진수로 변형하는 가장 기본적인 방법은, 해당 수를 2로 나누면서 나머지가 있을 경우 1을, 나머지가 없을 경우 0을 추가하는 행위를 반복하는 것이다. 예를들어, 21이라는 숫자가 있을 때, 이것을 2로 나누면 10이 되고 나머지가 발생한다(0 -> 1). 그리고 10을 2로 나누면 5가 되고 나머지가 발생하지 않는다(1 -> 10). 이런식으로 반복하면 10101 이 완성된다. 이를 코드로 표현하면 아래와 같다.
StringBuilder sb = new StringBuilder();
long num = numbers[i];
while(num > 0){
if(num % 2 == 1){
sb.insert(0,"1"); // 주어진 수를 2로 나누었을 때 1이 남을 경우, 이진수에 1을 추가
} else {
sb.insert(0,"0"); // 주어진 수를 2로 나누었을 때 나머지가 없는 경우, 이진수에 0을 추가
}
num /= 2; // 2로 나누어주고 반복
}
[2] 완전이진트리로 표현하기 위한 길이로 변경
완전이진트리는 이진트리의 리프노드까지 뻗어있는 이진트리를 의미한다. 완전이진트리로 표현하기 위해서는 길이가 1, 3, 7, 15, ... 가 되어야 하며 이는 $2^x - 1$ 형태가 된다. 아래 내용을 살펴보며 그 이유를 알아보자.
아래 그림과 같이 각각의 depth에 대해 노드는 $2^0$, $2^1$, $2^2$, $2^3$ 이 된다. 즉 $2^x$ 형태로 노드가 생겨나며, 모든 노드를 더하면 depth가 n일 때 모든 노드의 합은 $2^n-1$이 된다.(root의 depth를 1이라고 할 때)
이제 주어진 이진수를 완전이진트리로 표현 가능하도록 변경해 보자. 몇가지 예시를 들어보면 아래와 같다.
- 1101011(십진수 : 107) : 길이가 7 이므로 완전이진트리로 표현 가능.
- 10101 (십진수 : 21) : 길이가 5 이므로 완전이진트리로 표현 불가능. 2개의 '0'을 추가하여 0010101로 변경.
- 10001001 (십진수 : 137) : 길이가 8 이므로 완전이진트리로 표현 불가능. 7개의 '0'을 추가하여 000000010001001로 변경.
- 101010111010(십진수 : 2746) : 길이가 12 이므로 완전이진트리로 표현 불가능. 3개의 '0'을 추가하여 000 101010111010로 변경.
$n = 2^x$일 때, [1]에서 구한 이진수의 길이를 len 이라고 할 때, while문을 통해 $2^x-1 >= len$ 을 만족시킬 때까지 $n$ 즉, $2^x$ 값을 증가시킨다. 그리고 해당하는 $n$을 구하면 추가해야 하는 길이를 구한 뒤 이를 이진수 문자열에 더해준다. 이를 위한 코드는 아래와 같다.
int n=1;
int len = sb.length();
int addcnt; // 추가해야 할 길이
while(true){
n *= 2;
if(n - 1 >= len){ // 2^x-1 이 위에서 구한 이진수의 길이보다 크거나 같아질때까지 n(2^x)을 두 배로 증가시킨다.
addcnt = n-1-len; // 구한 n값에 대해 n-1에서 이진수 길이를 빼주어, 추가해야 할 길이를 구한다.
break;
}
}
for(int j=0; j<addcnt; j++){
sb.insert(0, "0"); // 추가해야 할 길이만큼 '0' 값으로 채운다.
}
[3] 완전이진트리로 구현이 가능한지 확인
2번에서 구한 이진값은 완전이진트리의 각 노드에 대입이 가능하다. 이 때, 이진값의 중간값을 기준으로 양쪽에 노드가 하나라도 존재한다면(양쪽에 하나라도 1인 수가 존재한다면), 중간값은 1이 되어야 한다. 이러한 원리는 중간 값을 기준으로 왼쪽 노드, 오른쪽 노드에도 동일하게 적용이 가능하다. 이런 방식으로 가장 마지막 자식 노드까지 범위를 좁혀나가며 위 조건을 만족하는지 살펴보고, 만족한다면 이진트리로 표현 가능한 수이고, 만족하지 않는다면 표현 불가능한 수가 된다. [2]의 네 번째 예시를 통해 그 원리를 살펴보자.
- 예시 : 000101010111010는 이진트리로 표현 가능한가?
000101010111010을 이진트리로 표현하면 아래와 같이 그려볼 수 있다. 이 때, 중간값(파란 블럭)을 기준으로 왼쪽, 오른쪽(녹색 블럭)에 하나라도 노드가 존재한다면 중간값은 1이어야 한다. 중간값이 만약 0이라면 자식 노드가 없다는 뜻이고, 그렇다면 양쪽에 노드가 존재할 수 없기 때문이다. 물론, 중간값이 1일 때 양쪽 노드가 없는 것은 가능하다.(자식 노드가 없을 경우가 이에 해당함)
한 depth를 더 내려가서, 양쪽 노드 각각을 조사해 보면, 아래와 같이 빨간 블럭(중간값)과 노란 블럭(왼쪽, 오른쪽 노드)을 비교해 볼 수 있다.
이를 반복하며 리프 노드에 도달할 때 까지 반복해 보면, 000101010111010 즉, 2746은 이진트리로 표현 가능한 숫자임을 알 수 있다.
이를 구현한 코드는 아래와 같다. 주어진 이진값의 왼쪽, 오른쪽 값이 valid 한지 구하기 위해 재귀 형태로 구현하였으며, 왼쪽+오른쪽 값이 0보다 크면서 중간값이 0일 경우 이진트리 형태로 표현이 불가하다고 판단하여, -1을 리턴하도록 하였다. 왼쪽+오른쪽+중간값이 0일 경우, 0을 리턴하며, 두 경우를 제외하고는 1을 리턴한다. 모든 재귀함수가 종료되고 최종적으로 -1이 리턴될 경우 이진트리로 표현 불가능한 수가 되며, 그 외 값(0, 1)은 이진트리로 표현 가능하다.
int sum(StringBuilder node){
int len = node.length();
if(len == 1){
return node.charAt(0) - '0'; // 자식 노드가 없다면, 해당 노드의 값(0 또는 1) 리턴
}
StringBuilder sbLeft = new StringBuilder(node.substring(0, len/2)); // 중간값 기준 왼쪽 노드
StringBuilder sbRight = new StringBuilder(node.substring(len/2+1)); // 중간값 기준 오른쪽 노드
int left = sum(sbLeft); // 왼쪽 노드 유효성 검사(재귀)
if(left == -1){
return -1; // 왼쪽 노드가 유효하지 않다면 -1 리턴
}
int right = sum(sbRight); // 오른쪽 노드 유효성 검사(재귀)
if(right == -1){
return -1; // 오른쪽 노드가 유효하지 않다면 -1 리턴
}
int mid = node.charAt(len/2) - '0'; // 중간값을 Int형으로 변경
if(left + right > 0 && mid == 0){
return -1; // 왼쪽, 오른쪽에 최소 1개의 노드가 존재하는데 중간값이 0일 경우 이진트리로 표현 불가능하므로 -1 리턴
} else if(left + right + mid == 0){
return 0; // 왼쪽, 오른쪽, 중간 모두 노드가 존재하지 않을 경우 이진트리로 표현 가능하나, 노드는 없으므로 0 리턴
} else {
return 1; // 그 외의 경우, 이진트리로 표현 가능하며 노드가 존재하기 때문에 1 리턴
}
}위와같이 sum함수를 통해 이진트리로 표현 가능한지, 불가능한지를 구한 후 아래와 같이 최종적으로 리턴할 배열에 넣어준다.(표현 가능할 경우 1, 불가능할 경우 0)
int ans = sum(sb);
if(ans == -1){
answer[i] = 0;
} else {
answer[i] = 1;
}
그렇다면, 최종적으로 전체 코드를 살펴보자.
class Solution {
public int[] solution(long[] numbers) {
int[] answer = new int[numbers.length];
for(int i=0; i<numbers.length; i++){
StringBuilder sb = new StringBuilder();
long num = numbers[i];
while(num > 0){
if(num % 2 == 1){
sb.insert(0,"1");
} else {
sb.insert(0,"0");
}
num /= 2;
}
int n=1;
int len = sb.length();
int addcnt;
while(true){
n *= 2;
if(n - 1 >= len){
addcnt = n-1-len;
break;
}
}
for(int j=0; j<addcnt; j++){
sb.insert(0, "0");
}
int ans = sum(sb);
if(ans == -1){
answer[i] = 0;
} else {
answer[i] = 1;
}
}
return answer;
}
int sum(StringBuilder node){
int len = node.length();
if(len == 1){
return node.charAt(0) - '0';
}
StringBuilder sbLeft = new StringBuilder(node.substring(0, len/2));
StringBuilder sbRight = new StringBuilder(node.substring(len/2+1));
int left = sum(sbLeft);
if(left == -1){
return -1;
}
int right = sum(sbRight);
if(right == -1){
return -1;
}
int mid = node.charAt(len/2) - '0';
if(left + right > 0 && mid == 0){
return -1;
} else if(left + right + mid == 0){
return 0;
} else {
return 1;
}
}
}