728x90
https://school.programmers.co.kr/learn/courses/30/lessons/150367
728x90
메모리: 95.9 MB
시간: 52.17 ms
와... 맨날 ide에서 개발하다가 프로그래머스로 문제 풀면 쉬운 문제도 풀기 힘든데, 이번 문제는 진짜 어려웠다.
일단 문제 이해부터 잘 못해서 두, 세번 코드 거의 갈아엎었다.
- numbers 안의 long 타입 변수들 for문으로 하나하나 접근하며 답을 구한다. (numbers[i]를 n에 저장)
- n이 1이면 무조건 노드가 1개인 이진트리로 표현할 수 있기 때문에 답에 1을 저장하고 다음 답을 구하러 넘어간다.
- n을 이진수 몇 자리로 표현 가능한지 구해주고 이를 cnt에 담는다. (ex. 58는 이진수로 111010이므로 6자리 표현 가능, cnt = 6)
- n을 포화이진트리로 만드려면 몇 자리로 표현해야 하는지 구해준다. 포화 이진트리는 $2^N - 1$개의 노드를 가지고 있으므로 cnt보다 큰 $2^N$ 중 가장 작은 수를 구하면 된다. 이를 leng에 저장해준다. (cnt = 6일 때, 포화이진트리로 표현하기 위해서는 노드가 $2^3 - 1$개 필요하므로 leng은 $2^3$)
- 각 leng 크기의 배열을 하나 선언해서 n을 이진수로 표현하여 각 자리에 잘 넣어준다. (ex. n = 58, 이진수로 표현하면 111010, 포화이진트리 형식으로 표현하기 위해서는 $2^3-1$로 표현해야 하므로 0111010, 이를 배열에 저장하면 [ 0, 1, 1, 1, 0, 1, 0], 이배열을 밑의 그림처럼 나타낼 수 있다.)
- 밑의 그림을 보면 알겠지만, 각 depth의 가장 왼쪽에 있는 노드는 항상 $2^N$이고, 해당 depth에 있는 노드들은 자신의 자식에 접근하려면 $2^{N - 1}$을 +, - 하면 된다.
- 위의 방법으로 자식 노드들에 접근하며 표현 가능한지 확인해준다. 현재 노드가 0일 때 자식 노드가 1이라면 표현 불가능한 이진트리가 된다. 또한 자식 노드와 인덱스가 1 차이 밖에 나지 않는다면, 자식 노드는 리프 노드이므로 더 이상 검사해주지 않아도 된다.
import java.util.*;
class Solution {
public int[] solution(long[] numbers) {
int[] answer = new int[numbers.length];
for(int i = 0; i < numbers.length; i++) {
long n = numbers[i];
if(n == 1) { // n이 1이면 아래의 과정을 거치지 않고 바로 다음 답 확인하러
answer[i] = 1;
continue;
}
// n을 이진수 몇 자리 수로 표현 가능한지 구하기
long temp = 1;
int cnt = 0;
while(n >= temp) {
temp *= 2;
cnt++;
}
// 포화이진트리를 만드려면 몇 자리 수로 표현해야 하는지 구하기
int leng = 1;
while(cnt >= leng) {
leng *= 2;
}
// 이진수로 표현한 n을 각 자리 수에 맞게 넣기
int[] node = new int[leng];
for(int j = 1; j <= leng - 1 - cnt; j++) node[j] = 0; // 포화이진트리를 만들기 위해 추가한 0
for(int j = leng - 1; j > leng - 1 - cnt; j--) {
node[j] = (int)(n % 2);
n /= 2;
}
// 루트노드부터 밑으로 내려가면서 부모 노드가 0이 아닌지 확인
Queue<int[]> q = new LinkedList<>();
q.add(new int[] {(leng + 1) / 2, (leng + 1) / 4}); // 현재 노드 번호(지금은 root)와 자식 노드와의 차이
boolean result = true;
while(!q.isEmpty()) {
int[] now = q.poll();
if(node[now[0]] == 1) { // 현재가 1이면 자식이 있던 없던 상관없음.
if(now[1] != 1) { // 자식 노드와 차이가 1이면 자식 노드는 리프 노드이므로 확인할 필요 없음
q.add(new int[] {now[0] - now[1], now[1] / 2}); // 왼쪽 노드
q.add(new int[] {now[0] + now[1], now[1] / 2}); // 오른쪽 노드
}
}
else { // 현재가 0이면 자식이 있으면 안됨.
if(node[now[0] - now[1]] == 1 || node[now[0] + now[1]] == 1) { // 자식이 있다면
result = false; // 이진트리로 표현 불가능
break;
}
else {
if(now[1] != 1) { // 자식 노드와 차이가 1이면 자식 노드는 리프 노드이므로 확인할 필요 없음
q.add(new int[] {now[0] - now[1], now[1] / 2}); // 왼쪽 노드
q.add(new int[] {now[0] + now[1], now[1] / 2}); // 오른쪽 노드
}
}
}
}
if(result) answer[i] = 1;
else answer[i] = 0;
System.out.println();
}
return answer;
}
}
728x90
'Problem Solving > Programmers' 카테고리의 다른 글
[프로그래머스, Lv.2] 조건에 부합하는 중고거래 상태 조회하기 (mysql) (0) | 2023.11.22 |
---|---|
[프로그래머스, Lv.1] 조건에 부합하는 중고거래 댓글 조회하기 (mysql) (0) | 2023.11.16 |
[프로그래머스, Lv.1] 개인정보 수집 유효기간 (java) (1) | 2023.10.26 |
[프로그래머스, Lv.4] 서울에 위치한 식당 목록 출력하기 (mysql) (0) | 2023.07.17 |
[프로그래머스, Lv.2] 3월에 태어난 여성 회원 목록 출력하기 (mysql) (0) | 2023.07.12 |