글 읽기 - '틀렸습니다' 라고 뜨네요 ㅠ

swrho 2년 전 0

질문1

일단 입력값 3개를 n 번 받고

'루트노드는 어떠한 노드의 자녀노드도 아니다' 라는 성질을 이용해서

2번째 3번째 입력값과 비교를 해서 찾았습니다.

이 과정에서 for 문을 2번 이용하는데요,

N 이 10000이고 최악의 경우 이중for문이기 때문에 O(N^2) 이 되고 그러면 1초가 넘어가지 않나요??

질문2

inorder 를 이용해 inorder 순서대로 열이되고

깊이를 함수의 입력값으로 들고가면서

깊이가 행이 된다는 생각으로 코드를 짰습니다.

잘 돌아가가고 디버깅에서도 문제 없었는데

어디가 틀렸는지 궁금합니다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdbool>

using namespace std;

struct Node {
	int r, c; // r -> depth , c -> inorder
}node[10005];
struct tree {
	int left, right;
}t[10005];
int N, pIdx = 1, maxH = -1;
int ans = -1;
void inorder(int cur, int depth) {
	if (cur == -1)
		return;

	inorder(t[cur].left, depth + 1);
	node[cur].r = depth;
	node[cur].c = pIdx++;
	inorder(t[cur].right, depth + 1);
	maxH = max(maxH, depth);
}
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int number, left, right;
		cin >> number >> left >> right;
		t[number].left = left;
		t[number].right = right;
	}
	//find root node
	int rootIdx = 0;
	for (int i = 1; i <= N; i++) {
		bool flag = false;
		for (int j = 1; j <= N; j++) {
			if (t[j].left == i || t[j].right == i)
			{
				flag = true;
				break;
			}
		}
		if (flag == false) {
			rootIdx = i;
			break;
		}
	}
	inorder(rootIdx, 1);	
	
	for (int i = 2; i <= maxH; i++) {
		int minC = 987654321, maxC = -1;
		for (int a = 1; a <= N; a++) {
			if (node[a].r == i) {
				minC = min(minC, node[a].c);
				maxC = max(maxC, node[a].c);
			}
		}
		int cha = maxC - minC + 1;
		ans = max(cha, ans);
	}
	for (int i = 2; i <= maxH; i++) {
		int minC = 987654321, maxC = -1;
		for (int a = 1; a <= N; a++) {
			if (node[a].r == i) {
				minC = min(minC, node[a].c);
				maxC = max(maxC, node[a].c);
			}
		}
		int cha = maxC - minC + 1;
		if (cha == ans) {
			cout << i << ' ';
			break;
		}
	}
	cout << ans;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

'틀렸습니다' 라고 뜨네요 ㅠ

swrho 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말