[백준/G5] 1068 트리

https://www.acmicpc.net/problem/1068

삭제된 노드가 주어지면, 이를 반영한 트리의 리프노드의 개수를 구해야함

python

31120kb 40ms Python 3

def remove_effect(remove):
    # 삭제된 노드를 -2로 표시, -1이 아닌 이유는 루트노드만 남아있는 경우가 있기 때문
    parent[remove] = -2 

    # for i, p in enumerate(parent):
    #     if p == remove:
    #         remove_effect(parent, i)

    for i in range(N):
    	# 어떤 부모가 삭제노드이면 재귀로 
        if remove == parent[i]:
            remove_effect(i)


import sys
input = sys.stdin.readline

N = int(input())
parent = list(map(int, input().split()))
remove_node = int(input())

# 삭제노드 반영
remove_effect(remove_node)


# 리프노드 찾기
cnt = 0
for i in range(N):
    if parent[i] != -2 and i not in parent:
        cnt += 1


print(cnt)

JS

파이썬이랑 똑같이 구현 + includes대신 set(O(1))으로 푸는게 더 빠름

9340kb 132ms node.js

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().split("\n");

const N = parseInt(input[0]);
const parent = input[1].split(' ').map(Number);
const removeNode = parseInt(input[2]);

const removeEffect = (remove) => {
	parent[remove] = -2;

	// 삭제노드를 부모로 가진 모든 자식노드의 부모를 재귀를 통해 -2로 업데이트
	for (let i = 0; i < N; i++) {
			if (remove === parent[i]) {
					removeEffect(i);
			}
	}
}

removeEffect(removeNode);

// 해당 노드의 부모가 삭제 되지 않았음 && 해당 노드의 자식노드가 존재하지 않을 때 
let cnt = 0

// 이것도 가능하지만 set을 쓰는게 더 빠름
// for (let i = 0; i < N; i++) {
//     if (parent[i] !== -2 && !parent.includes(i)) {
//         cnt++;
//     }
// }

const parentSet = new Set(parent);

for (let i = 0; i < N; i++) {
    if (parent[i] !== -2 && !parentSet.has(i)) {
        cnt += 1;
    }
}


console.log(cnt)