문제 설명
포화 이진 트리에서 높이가 n일 때 전체 노드의 개수를 구한다. 결과 값은 값이 오버플로우를 방지하기 위해 1,000,000,007로 나눈 나머지 값을 반환한다.
포화 이진 트리
포화 이진 트리(飽和二進-, 영어: perfect binary tree)는 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다(이는 애매모호하게 완전 이진 트리라고도 불린다). (wikipedia)
입출력 예시
입력: n = 5
출력: 31
풀이 과정
높이가 n인 포화 이진 트리의 모든 노드 수를 계산하고, 그 결과를 1,000,000,007로 나눈 나머지를 반환하는 문제입니다.
왜 1,000,000,007 인가?
10억보다 큰 소수이기 때문에 이 값으로 나머지 연산을 해서 값을 얻으면 큰 범위의 정수도 표현이 가능하다. 어떤 큰 수를 계산하더라도 최종 결과는 항상 0에서 1,000,000,006 사이의 값을 얻게 된다.
먼저 포화 이진 트리라는 조건이 주어졌으니, 이 특징을 활용해서 노드의 수를 계산할 수 있을지 고민해보아야 합니다.
포화 이진 트리의 특성 고려하기
높이가 5인 포화 이진 트리의 노드 개수는 아래와 같습니다. (높이 1 = level 0)
- 높이가 1일 때 노드 개수 1
- 높이가 2일 때 노드 개수 2
- 높이가 3일 때 노드 개수 4
- 높이가 4일 때 노드 개수 8
- 높이가 5일 때 노드 개수 16
2^높이 값이 해당 높이의 총 노드 개수입니다. 즉, 높이가 하나씩 높아질 수록 지난 노드 개수에서 2배씩 늘어납니다.
계산 값이 커져서 int를 사용할 수 없을 경우를 고려하기
제곱 계산을 반복하기 때문에 결과 값이 너무 커지는 경우가 생길 수 있습니다. 로직에서 결과 값을 담는 아래 두 변수의 타입을 고민해야 합니다.
total: 전체 노드 수를 저장할 변수입니다.nodes: 현재 레벨의 노드 수를 저장합니다.
노드 개수와 관련된 변수는 값이 커질 수 있기 때문에 long으로 선언합니다.
루프를 이용해서 누적된 총 노드 개수를 계산
레벨을 증가시키면서 각 레벨의 노드 수를 total에 누적해서 더합니다. 다음 레벨 노드 수는 * 2로 미리 구한 다음, 다음 루프를 돌 때 그 값이 누적되는 방식으로 처리했습니다.
사실 Math.pow()를 사용해서 제곱 값을 쉽게 구하는 걸 먼저 생각했는데, 이 방식은 부동 소수점 연산 방식으로 계산이 되고 결과 값도 double로 반환한다는 걸 알게됐습니다. 2의 제곱을 하는 연산은 항상 정수 값을 결과로 반환하지만, 이 메소드를 사용하면 아주 큰 숫자를 다룰 때 소수점이 있는 숫자로 반환하는 과정에서 작은 오차가 생길 수 있어 사용하지 않았습니다.
부동 소수점
컴퓨터가 실수를 저장하고 계산하기 위해 사용하는 방식. 아주 큰 숫자나 소수점 아래 많은 자릿수를 가진 숫자를 표현할 수 있게 한다. 하지만 컴퓨터는 메모리에 숫자를 저장할 때 비트 0과 1만 사용하므로, 아주 긴 숫자는 메모리에 다 저장하지 못할 수 있고 그 경우 일부 숫자가 잘린다. 이 경우 근사값으로 저장되어 정확도가 떨어질 수 있다.
두 long 변수는 값을 구할 때마다 mod 값으로 나머지 연산을 적용했습니다. long 타입으로 지정했지만 2^61부터는 long 타입 범위를 초과할 가능성이 있습니다. 매번 나머지 연산이 자동으로 수행되도록 코드를 작성했기 때문에, 오버플로우가 발생해서 잘못된 결과 값이 나오는 것을 방지할 수 있게 됩니다.
마지막으로 주어진 높이까지 루프를 반복하면, 전체 노드 수는 int 로 반환해야 하기 때문에 형변환을 시켜줍니다.
전체 코드
class Solution {
public int solution(int n) {
int mod = 1_000_000_007;
long total = 0; // 전체 노드 개수의 합
long nodes = 1; // 해당 높이의 노드 개수를 저장할 변수, 레벨 1의 노드 개수 1로 초기화
for (int i = 1; i <= n; i++) {
total = (total + nodes) % mod;
nodes = (nodes * 2) % mod; // 다음 레벨의 노드 수
}
return (int) total;
}
}