[C] 백준 | 10816번 코드 - 숫자 카드 2

>문제

> 핵심

이진탐색 / 이진탐색트리..?

>풀이과정

처음에는 배열을 list[50만][2] 짜리로 선언을 해서, 입력받은 정수와, 개수를 묶어서 탐색을 하려고 했었는데,

이중반복문을 돌아야할 것 같아서 다른 방법을 곰곰이 생각하다가,,

화장실에서 문득 이진트리! 생각이 나서 이진탐색트리 방법으로 풀었는데 다행히 정답이 나왔다.

 

같은 카드를 여러장 가지고 있을 수 있으므로, 값이 중복해서 들어오는 경우를 대비해 노드에 cnt 변수를 추가하여

같은 값이 들어올 때 cnt+=1만 하고 노드를 따로 생성하지는 않는 코드만 살짝 추가했다.

 

이진탐색트리는

최선의 경우(양쪽으로 잘 분배된 경우) O(logn),

최악의 경우(한쪽으로 쏠린경우) O(n)의 시간복잡도를 갖는다. -> 이를 해결하기 위해 양쪽 균형이 깨질때마다 트리를 조정하는 AVL 트리가 있는데,, 생각하면 머리아파서 못만들겠다. LL 회전 RL 회전.. 어휴 골때린다. 참고로 O(logn)

 

그리고 문제와는 별개로 이진탐색트리를 중위순회(inorder)하면 오름차순으로 출력이 된다.

 

· 전위순회 (preorder) : V-L-R

· 중위순회 (inorder) : L-V-R

· 후위순회 (postorder) : L-R-V

 

코드를 짜는거는 그냥 printf 위치만 살짝 바꿔주면 된다.

void preorder(TreeNode* Root) // VLR
{
	if (Root != NULL)
	{
		printf("%d ", Root->data);
		preorder(Root->left);
		preorder(Root->right);
	}
}

void inorder(TreeNode* Root) // LVR
{
	if (Root != NULL)
	{
		inorder(Root->left);
		printf("%d ", Root->data);
		inorder(Root->right);
	}
}

void postorder(TreeNode* Root) // LRV
{
	if (Root != NULL)
	{
		postorder(Root->left);
		postorder(Root->right);
		printf("%d ", Root->data);
	}
}

 

근데 문제를 풀고나서 다른사람이 짠 코드를 검색해 봤는데 나처럼 푼사람이 아무도 없었다.

원래 이렇게 푸는 문제가 아닌가?

일반적인 이진탐색 알고리즘을 쓰면 틀린다고 하는데 난 맞았다..?

이분탐색을 변형한 upper bound, lower bound를 사용해야 한다고 하는데 난생 처음들어본다..

코린이는 아무것도 몰라요.. 나중에 알아보자..

>깨달은점

입력받는 정수의 범위가 - 부터 + 까지 양쪽으로 매우 넓게 주어지는 문제라면 앞으로 이진탐색을 먼저 생각해봐야겠다.

 

>코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
	struct TreeNode* left;
	struct TreeNode* right;
	int key;
	int cnt;
}TreeNode;

TreeNode* insert_Node(TreeNode* Root, int key)
{
	if (Root == NULL)
	{
		TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));
		tmp->left = tmp->right = NULL;
		tmp->key = key;
		tmp->cnt = 1;

		return tmp;
	}

	if (key < Root->key)
		Root->left = insert_Node(Root->left, key);
	else if (key > Root->key)
		Root->right = insert_Node(Root->right, key);
	else if (key == Root->key)
		Root->cnt += 1;

	return Root;
}

TreeNode* Search(TreeNode* Root, int key)
{
	if (Root == NULL)
		return NULL;

	if (Root->key == key)
		return Root;
	else if (Root->key < key)
		return Search(Root->right, key);
	else
		return Search(Root->left, key);
}

int main()
{
	TreeNode* Root = NULL, * tmp = NULL;
	int N, M, i, j, e;

	scanf("%d", &N);

	for (i = 0; i < N; i++)
	{
		scanf(" %d", &e);
		Root = insert_Node(Root, e);
	}

	scanf(" %d", &M);

	for (i = 0; i < M; i++)
	{
		scanf(" %d", &e);
		tmp = Search(Root, e);

		if (tmp == NULL)
			printf("0 ");
		else
			printf("%d ", tmp->cnt);
	}

	return 0;
}