백준 12767 : Ceiling Function

www.acmicpc.net/problem/12767

12767번: Ceiling Function

주어지는 수로 이진트리를 만들고 나올 수 있는 이진트리의 모양의 수를 찾는 문제이다.

 

#include <iostream>
#include <set>
#include <bitset>
#include <cstring>

#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

//트리 높이가 최대 20까지 나올 수 있으므로 이진트리 노드의 개수는 최대 2^20개
const int MAX = (1 << 20) + 1;
set<int> shape;
bitset<MAX> bst;
hash<bitset<MAX>> bit_hash;
int tree[MAX];

int main() {
	fastio;
	int n, k, num, idx;
	cin >> n >> k;
	while (n--) {
		for (int i = 0; i < k; i++) {
			cin >> num;
			idx = 1;
            		//이진트리 자리 찾아가기
			while (tree[idx] != 0) {
				if (tree[idx] > num) idx *= 2;
				else idx = 2 * idx + 1;
			}
			tree[idx] = num;
			bst[idx] = 1;
		}
        	//bit를 2진수로 표현하면 2^(2^20) ... 1 까지이기 때문에 hashing을 해서 set에 넣어줌
		shape.insert(bit_hash(bst));
		bst.reset();
		memset(tree, 0, sizeof(tree));
	}
	cout << shape.size();
	return 0;
}

메모리: 6244 KB

시간: 12 ms

이진트리에서 자식 노드의 인덱스는 현재 노드의 번호가 idx라고 할 때 왼쪽 자식은 2*idx, 오른쪽 자식은 2*idx + 1이 되므로 위와 같은 방법으로 이진트리를 만들어주고 hashing과 set을 이용하여서 나올 수 있는 트리의 모양의 가지 수를 찾는다.

코드는 짧지만 메모리와 시간 적인 측면에서 효율적이지 못하다. 다른 분들은 2000초반 KB에 0 ms로 풀었던데 배워와야겠다.