Skip to main content Link Menu Expand (external link) Document Search Copy Copied
Hepheir

1233. 사칙연산 유효성 검사

Code Battle (`23 동계 대학생 S/W 알고리즘 특강 기초학습 문제)

본 게시글은 개인 학습 용도로 작성한 게시글입니다.

(문제 출처: SW Expert Academy)

  • 분할 정복 + 트리 순회 (post-order) 문제.
  • 완전 이진 트리이므로, 배열로 트리 구현이 가능하다.
  • 노드 번호와, 자식 노드의 번호는 예측 가능하므로 입력받지 않고 무시하였다. cin.ignore() 사용.
  • 재귀호출을 이용하여 post order 순회를 구현하였다.
  • 어떤 노드에서 해당 식이 유효한 지 검사하는 방법은 다음과 같다:
    • 1. 어떤 노드의 자식이 하나도 없다면, 해당 노드는 숫자여야만 유효한 식이 된다.
    • 2. 어떤 노드의 자식이 하나만 있다면, 피연산자가 모자라서 식이 완성되지 못하므로 유효하지 않은 것이다.
    • 3. 어떤 노드의 자식이 둘 다 있다면, 두 자식 모두 1, 2, 3 중 하나에 대하여 유효한 식이어야 한다.
  • 위의 검사를 재귀적으로 수행하면 분할 정복 문제로서 이 문제를 풀이 할 수 있다.
#include <cctype>
#include <string>
#include <iostream>

#define MAX_N 200
#define ANSWER_POSSIBLE 1
#define ANSWER_IMPOSSIBLE 0

using namespace std;

int treeSize;
char tree[MAX_N + 1];

int left(int i)
{
	return i << 1;
}

int right(int i)
{
	return (i << 1) + 1;
}

bool has(int i)
{
	return i <= treeSize;
}

bool is_leaf(int i)
{
	return !has(left(i));
}

bool has_both_children(int i)
{
	return has(left(i)) && has(right(i));
}

bool post_order(int i)
{
	if (is_leaf(i))
	{
		return isdigit(tree[i]); // Leaf 노드는 항상 숫자여야함.
	}
	if (has_both_children(i))
	{
		return post_order(left(i)) && post_order(right(i));
	}
	return false; // 피연산자가 하나 밖에 없으면 불가능.
}

static int solve()
{
	int i;
	cin >> treeSize;
	cin.ignore();
	for (i = 1; i <= treeSize; i++)
	{
		cin.ignore(4, ' ');
		cin >> tree[i];
		cin.ignore(16, '\n');
	}
	return post_order(1) ? ANSWER_POSSIBLE : ANSWER_IMPOSSIBLE;
}

int main(int argc, char **argv)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	for (int test_case = 1; test_case <= 10; ++test_case)
	{
		printf("#%d %d\n", test_case, solve());
	}
	return 0;
}

Back to top