프로그래머스 문제
https://school.programmers.co.kr/learn/courses/30/lessons/150367
풀이 후기
1. 분석
카카오 문제는 글이 너무 어려워서 풀기가 싫다. 아무튼, 포화 이진 트리(모든 리프 노드의 레벨이 같고 인터널 노드의 자식이 2개씩 있는 트리)를 중위순회 했을 때, 나올 수 있는 숫자인가 찾는 문제이다.
이진수로 변환하는 과정은 너무 많으니 넘어가고, 정답을 찾는 방법은 [1 ≤ numbers의 원소 ≤ 10^15] 조건이 걸려 있기 때문에 진짜 모든 트리를 그려서 풀지 말라는 카카오의 뜻을 알 수 있으며, 주어진 숫자를 이진수로 바꿔서 조건에 맞는지 찾으면 된다. 근데 여기서 또 문제는 주어진 조건이...
- 이진수를 저장할 빈 문자열을 생성합니다.
- 주어진 이진 트리에 더미 노드를 추가하여 포화 이진 트리로 만듭니다. 루트 노드는 그대로 유지합니다.
- 만들어진 포화 이진 트리의 노드들을 가장 왼쪽 노드부터 가장 오른쪽 노드까지, 왼쪽에 있는 순서대로 살펴봅니다. 노드의 높이는 살펴보는 순서에 영향을 끼치지 않습니다.
- 살펴본 노드가 더미 노드라면, 문자열 뒤에 0을 추가합니다. 살펴본 노드가 더미 노드가 아니라면, 문자열 뒤에 1을 추가합니다.
- 문자열에 저장된 이진수를 십진수로 변환합니다.
이 글에서 정답을 찾는 건 포기했고 그냥 테스트케이스를 보면서 천천히 풀어봤다.
- 아무튼, 1로만 채워진 이진 트리가 있다.
- 포화이진 트리가 되도록 빈 곳을 0으로 꽉꽉 채운다.
- 그렇기에 1 -> 0 -> 1 같은 경로는 나올 수 없다. (핵심 조건)
그래서 이 조건을 가지고 첫 번째로 풀어본 것은 ＇리프 노드 아닌데 0 있으면 틀린 숫자＇ 였다. 그리고 해당 지점이 리프 노드인지 찾는 작업은 중심 지점에서부터, n / 2씩 재귀로 탐색하면서 찾도록 했다. 8에서부터 -4, +4지점을 탐색, 4에서부터 -2, +2지점을 탐색... 이하 반복해서 1이 되면 리프 노드인 걸로.
그리고 당연히 틀렸다. 요건 테스트케이스만 너무 보다가 틀린 예시. 리프 노드 아니면 0이 안되지 않나? 생각할 수 있지만, 부모가 0이면 자식이 둘 다 0일 수도 있다. 질문하기 보니까 나처럼 테케 1번만 맞고 다 틀려서 질문하러 온 사람들이 많았다.
그래서 다시 풀려고 했는데 탐색 과정을 재귀로 만들다보니 bool과 자신의 숫자를 넘기는게 좀 복잡해졌고, 생각을 좀 해서 조건을 재정립 했다. [부모는 자식들의 숫자 이상이여야 한다.] 이걸 활용해서 조건이 맞으면 -> 내 숫자를 리턴, 조건이 틀리면 -> 2를 리턴. 2를 리턴하는 이유는 노드의 값이 0, 1 밖에 없기 때문에 절대 2를 넘을 수 없기 때문이다. 다행히 조건만 문제였는지 금방 풀렸다.
2. 실행 결과
3. 코드
using System;
using System.Collections.Generic;
using System.Linq;
public class Solution
{
private int[] NodeCount = { 0, 1, 3, 7, 15, 31, 63 };
public int MakeBinary(long n)
{
// 시프트를 통해 이진수를 큐에 채웁니다.
var binary = new Queue<int>();
while (0 < n)
{
binary.Enqueue((int)(1 & n));
n >>= 1;
}
// 층마다 커버할 수 있는 이진수 길이를 확인합니다.
var target = 0;
while (NodeCount[target] < binary.Count)
{
target++;
}
// 원활한 탐색을 위해 0번을 비우고 새로운 배열을 제작합니다.
var nodeAmount = NodeCount[target] + 1;
var newBinary = new int[nodeAmount];
// 시프트 연산은 앞 부터 진행. 그냥 큐에 넣은 순서대로 꺼내서 뒤에 넣으면 됩니다.
for (var i = nodeAmount - 1; i >= 0; i--)
{
if (0 < binary.Count)
{
newBinary[i] = binary.Dequeue();
}
else
{
break;
}
}
return SearchNode(newBinary, nodeAmount / 2, nodeAmount / 2) == 2 ? 0 : 1;
}
public int SearchNode(int[] arr, int n, int len)
{
// 리프 노드는 볼 필요 없음.
if (len == 1)
{
return arr[n];
}
// 중앙부터 len이 2배로 작아지면서 탐색됩니다.
var newLen = len / 2;
var left = SearchNode(arr, n - newLen, newLen);
var right = SearchNode(arr, n + newLen, newLen);
// 자식 노드는 자신보다 작거나 같아야함. 2를 리턴하면 그냥 터진것
if (left <= arr[n] && right <= arr[n])
{
return arr[n];
}
return 2;
}
public int[] solution(long[] numbers)
{
return numbers.Select(MakeBinary).ToArray();
}
}위에 NodeCount는 주석에도 있듯이 층에 해당하는 포화이진트리의 총 노드 갯수다. 최대값인 10^15 = 0011100011010111111010100100110001101000000000000000인데, 52자리여서 6층으로 커버 가능하다. 당연히 최소 이진수의 자릿수만큼의 노드가 필요하기 때문에 계산용.
근데 카카오코테 진짜 어캐 푸는거임?? 쫄려서 못 풀거같다.
