Portfolio

풀이

현석


// Run by Node.js
const readline = require('readline');

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	
	let index = 0
	let N, M
	const lines = []
	
	rl.on('line', (line => {
		if (index === M + 1) rl.close()
		index++
		if (index === 1) {
			[N, M] = line.trim().split(' ').map(Number)
		} else {
			lines.push(line.trim().split(' ').map(Number))
		}
	}))
	
	rl.on('close', () => {
		solution(N, lines)
		process.exit();	
	})
})();

function solution(N, lines) {
	const events = new Array(N + 1).fill(0)
	lines.forEach((line) => {
		line.forEach((event, index) => {
			if (index === 0) return
			events[event] += 1	
		})
	})
	
	const max = Math.max(...events)
	const popularEvent = events.flatMap((event, index) => {
		return max === event ? [index] : []
	}).reverse().join(' ')
	
	console.log(popularEvent)
}


// Run by Node.js
const readline = require('readline');

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	
	let N, M
	let index = 0
	const links = []

	
	rl.on('line', line => {
		index++
		if (index === M + 3) rl.close()
		if (index === 1) {
			N = +line.trim()
		} else if (index === 2) {
			M = +line.trim()
		} else {
			links.push(line.trim().split(' ').map(Number))
		}
	})
	
	rl.on('close', () => {
		solution(N, links)
		process.exit();
	})
})();

function solution(N, links) {
	const adjGraph = new Map()
	
	links.forEach(([node1, node2]) => {
		if (!adjGraph.has(node1)) adjGraph.set(node1, new Set())
		if (!adjGraph.has(node2)) adjGraph.set(node2, new Set())
		
		adjGraph.get(node1).add(node2)
		adjGraph.get(node2).add(node1)
	}) 
	
	const visit = new Array(N + 1).fill(false)
	visit[0] = true

	const stack = [1]
	let count = 0
	
	while (stack.length) {
		const node = stack.pop()
		if (visit[node]) continue
		visit[node] = true
		count++
		
		if (!adjGraph.has(node)) continue
		const adjNodes = adjGraph.get(node).forEach(node => stack.push(node))
	}
	
	console.log(count)
}


// Run by Node.js
const readline = require('readline');

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	
	let index = 0
	let N, M, K
	
	const bridges = []
	
	rl.on('line', line => {
		if (index === 0) {
			[N, M, K] = line.trim().split(' ').map(Number)			
		} else {
			bridges.push(line.trim().split(' ').map(Number))
		}
		
		if (index === M) rl.close()
		index++
	})
	
	rl.on('close', () => {
		solution(N, K,bridges)
		process.exit()
	})
})();

function solution(N, K, bridges) {
	const adjGrapah = new Map()
	
	bridges.forEach(([node1, node2]) => {
		if (!adjGrapah.has(node1)) adjGrapah.set(node1, new Set())
		
		adjGrapah.get(node1).add(node2)
	})
	
	const visit = new Array(N + 1).fill(false)
	visit[K] = true
	let min = 10000
	
	
	const backTracking = (currNode, count) => {
		if (count >= min) return
		
		if (visit[currNode] || !adjGrapah.has(currNode)) return
		visit[currNode] = true
		
		const nextNodes = adjGrapah.get(currNode)
		nextNodes.forEach(nextNode => {
				if (nextNode === K) {
					min = Math.min(min, count + 1)
					return
				}		
			
			backTracking(nextNode, count + 1)
		})
		visit[currNode] = false
	}
	
	if (adjGrapah.has(K)) {
		adjGrapah.get(K).forEach(next => {
			backTracking(next, 1)
		})
	}

	console.log(min === 10000 ? -1 : min)
}

재영


// Run by Node.js
const readline = require('readline');

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	const inputs = []
	rl.on('line', (line) => inputs.push(line)).on('close', () => {
		main(inputs);
		
		process.exit();
	})
})();

function main(inputs) {
	const [N, M] = inputs[0].split(' ').map(Number);
	const evts = new Array(N + 1).fill(0);
	
	for (let i = 1; i < M + 1; i += 1) {
		const now = inputs[i].split(' ').slice(1).map(Number);
		now.forEach((v) => evts[v] += 1);
	}
	
	const maxValue = Math.max(...evts)
	
	const results = [];
	evts.forEach((v, idx) => {
		if (v === maxValue) results.unshift(idx);
	})
	
	console.log(results.join(' '))
}


// Run by Node.js
const readline = require('readline');

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	
	const inputs = [];
	
	rl.on('line', (line) => inputs.push(line)).on('close', () => {
		main(inputs);
		process.exit();
	})
})();

const findParent = (parent, x) => (parent[x] === x) ? x : findParent(parent, parent[x]);

const updateParent = (parent, a, b) => {
  const parentA = findParent(parent, a);
  const parentB = findParent(parent, b);
  if (parentA < parentB) parent[parentB] = parent[parentA];
  else if (parentB < parentA) parent[parentA] = parent[parentB];
}

function main(inputs) {
	const N = +inputs[0];
	const M = +inputs[1];
	
	const parents = Array.from({ length: N + 1 }, (_, idx) => idx);
	
	for (let i = 2; i < M + 2; i += 1) {
		const [a, b] = inputs[i].split(' ').map(Number);
		
		updateParent(parents, a, b);
	}
	
	const networkStandard = 1;

	console.log(parents.filter(v => findParent(parents, v) === networkStandard).length)
}

런타임 에러 케이스 1) 메모리를 굉장히 작게 줘서, array로 visited 검사 시 메모리가 터진다.

런타임 에러 케이스 2) concat 메서드를 사용할 때 오류가 발생한다.

해결 1) Set 자료구조를 활용한다.

해결 2) concat 대신 Nullish coalescing Operator을 활용한다.

결론: BFS 문제라면서, 자바스크립트에게만 유독 박한 구름 😥


// Run by Node.js
const readline = require('readline');

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	const inputs = [];
	
	rl.on('line', line => inputs.push(line.trim()))
	
	rl.on('close', () => {
		main(inputs);
		process.exit();
	})
})();


class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }
  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }
  get length() {
    return this.rear - this.front;
  }
}

function main(ips) {
	let result = -1;
	
	const [N, M, K] = ips[0].split(' ').map(Number);
	const graph = {};
	
	for (let i = 1; i < M + 1; i += 1) {
		const [a, b] = ips[i].split(' ').map(Number);
		graph[a] = [...(graph[a] ?? []), b];
	}
	
	const queue = new Queue();
	if (graph[K]) {
		for (let now of graph[K]) {
			queue.enqueue([now, 1, new Set()]);
		}		
	}
	
	while (queue.length) {
		const [now, cnt, visited] = queue.dequeue();
		visited.add(now);
		
		if (now === K) {
			result = cnt;
			break;
		}
		
		if (graph[now]) {
			for (const v of graph[now]) {
				if (visited.has(v) === false) {
					queue.enqueue([v, cnt + 1, new Set(visited.entries())])
				}
			}
		}
	}
	
	console.log(result);
}

구름 코테 7주차

풀이