2022-07-07T22:47:07.989Z

0

굳이 사이즈를 더 할 필요없이 size가 0일때만 더해주면 됐군요... 머리를 탁..!

로직을 변경을 해도 계속 78%에서 틀려서 여러 시도 끝에 반례를 찾았습니다

input

4

-1 0 1 2

2 

output

1 이 나와야함 // 제 코드는 0이 나오더군요

트리가 직선 모양 일 때 잘못된 답이 나왔습니다. 

그래서 vst배열을 사용하지 않고 v[지우는 노드].clear() 로 size를 0으로 만들어준 뒤 v[지우는노드] 를 부모로 가지는 자식 노드들도 벡터에서 지워주었습니다.

아래는 저의 코드입니다

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int n;
int cnt;
queue<int> q;
int root;
int main(void){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	vector<int> v[n];
	for(int i=0; i<n; i++){
		int x;
		cin >> x;
		if(x == -1){
			q.push(i);
			root = i;
		}
		else{
			v[x].push_back(i);
		}
	}
	int rn;
	cin >> rn;
	if(rn == root){
		cout << 0;
		return 0;
	}
	if(n == 2){
		cout << 1;
		return 0;
	}
	v[rn].clear();
	for(int i=0; i<n; i++){
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == rn) v[i].erase(v[i].begin()+j);
		}
	}
	while(!q.empty()){
		auto cur = q.front(); q.pop();
		for(int j=0; j < v[cur].size(); j++){
			cnt += (v[v[cur][j]].size() == 0);
			q.push(v[cur][j]);
		}
	}
	cout << cnt;
	return 0;
}

0

음... 이 코드 혹시 맞나요? / 제가 보기에는... 한단계밖에 조사를 하지 않는 거같아요. 자 예를 들어서 1 2 3 4가 일자로 연결되어있고(1 - 2 - 3 - 4 / 4가 가장 부모노드) 4가 remove 노드라면 어떻게 되나요? 단순히 2중 for문으로 해당 부분이 다 제거가 안 될 것같아요. 예를 들어 1 - 2 가 제거가 되나요? 

지금 "제거"하는 로직 자체가 올바르게 되지않았다는 말씀을 드리구요.

"제거" 문제는 사실 굉장히 까다로워요. 꼭 필요한 경우에는 "제거" 로직을 넣지만 보통은 제거 보다는 "표기"를 해서 해당 부분에 대한 로직을 진행하지 않거나 하는 경우로 합니다. :)

감사합니다. 

강사 큰돌 올림.

0

제출 했을때는 정답처리가 되었습니다. 아하..! 저는 항상 부모노드가 자식노드 보다 작은 수를 가진다고 생각하고 문제를 풀었습니다. 문제에서는 부모노드는 자식노드보다 숫자가 작다 라는  조건이 없군요... 표기 방식 머릿속에 메모해두겠습니다! 많은 공부가 된 거 같습니다 큰돌 강사님. 답변 감사합니다 !!