[구름/JavaScript] 알고리즘 먼데이 챌린지 3주차

챌린지 소개

구름LEVEL

 

문제 및 해설

알고리즘 {먼데이} 챌린지 해설 - 구름EDU

 

10월 3일부터 12월 4일까지 구름LEVEL에서 알고리즘 먼데이 챌린지를 진행하고 있습니다. 8주 동안 매주 월요일마다 새로운 문제가 출제되는데 문제를 풀거나 이전 주의 문제를 복습하면 스탬프를 모을 수 있습니다. 스탬프 개수에 따라 다양한 상품도 받을 수 있어서 알고리즘 공부에 대한 동기 부여도 되고 재밌게 도전해볼 수 있을 것 같아요!

 

개별 문제는 https://level.goorm.io/에서 문제명을 검색하면 풀어볼 수 있습니다.

 

---

 

챌린지 3주차(10월 17일-23일) 복습 후 풀이를 공유합니다. 더 자세한 풀이는 위 해설을 참고하시길 바랍니다.

백준처럼 readline으로 입력을 받아서 처리합니다. 문제 해결에 필요한 로직은 solution 함수로 분리했습니다.

 

문제 1. 0커플

	const readline = require('readline');
	(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	const input = [];
	for await (const line of rl) {
	if (input.length) {
	input.push(line.split(' ').map((v) => +v));
	rl.close();
	} else {
	input.push(+line);
	}
	}
	console.log(solution(...input));
	process.exit();
	})();
	function solution(arr) {
	return arr.reduce((acc, v) => acc + v, 0);
	}
	// 테스트
	console.log(solution(8, [1, 2, 3, 4, -1, -2, -3, -5])); // -1
	console.log(solution(8, [-1, 1, 2, -2, 3, -3, 4, 5])); // 9

view raw solution.js hosted with ❤ by GitHub

n점이 있다면 -n이 항상 존재한다는 규칙을 지키지 못했다고 했으므로, arr 배열 원소의 총합이 곧 소개팅을 진행하지 못한 사람의 점수 합이 됩니다. 배열 원소의 합을 구하기 위해 reduce()를 사용했습니다.

 

reduce()의 첫 번째 인자로 반환값을 누적하는 콜백 함수를, 두 번째 인자로 초깃값 0을 넘겨줍니다.

 

 

문제 2. 폴더 폰 자판

	const readline = require('readline');
	(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	const input = [];
	for await (const line of rl) {
	input.push(line);
	if (input.length === 2) rl.close();
	}
	console.log(solution(+input[0], input[1]));
	process.exit();
	})();
	function solution(n, s) {
	const keyboard = {
	1: '1.,?!',
	2: '2ABC',
	3: '3DEF',
	4: '4GHI',
	5: '5JKL',
	6: '6MNO',
	7: '7PQRS',
	8: '8TUV',
	9: '9WXYZ',
	};
	let answer = '';
	let count = 0;
	for (let i = 0; i < n; i++) {
	if (s[i + 1] === s[i]) {
	count++;
	} else {
	count %= keyboard[+s[i]].length;
	answer += keyboard[+s[i]][count];
	count = 0;
	}
	}
	return answer;
	}
	// 테스트
	console.log(solution(2, '11')); // .
	console.log(solution(14, '44433355556666')); // HELO

view raw solution.js hosted with ❤ by GitHub

챌린지 2주차 문제2 철자 분리 집합 문제를 응용한 문제입니다.

 

주어진 문자열을 순회하면서 현재 숫자와 다음 숫자가 일치하면 count를 1 증가시킵니다. 일치하지 않으면 count를 현재 숫자로 입력할 수 있는 문자 종류의 개수로 나눠 몇 번째 문자인지 찾고 answer 문자열에 붙입니다.

 

문자열 순회 시 문자열 앞에 +을 붙여 편리하게 숫자로 형변환했습니다.

 

 

문제 3. 구름이의 여행

	const readline = require('readline');
	(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	let n, m, k;
	const input = [];
	for await (const line of rl) {
	if (m) {
	input.push(line.split(' ').map((v) => +v));
	if (input.length === m) rl.close();
	} else {
	[n, m, k] = line.split(' ').map((v) => +v);
	}
	}
	console.log(solution(n, m, k, input));
	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++;
	return value;
	}
	size() {
	return this.rear - this.front;
	}
	}
	function solution(n, m, k, arr) {
	const graph = Array.from(Array(n + 1), () => []);
	arr.forEach(([u, v]) => {
	graph[u].push(v);
	graph[v].push(u);
	});
	const queue = new Queue();
	const visited = Array.from({ length: n + 1 }, () => -1);
	queue.enqueue(1);
	visited[1] = 0;
	while (queue.size()) {
	const current = queue.dequeue();
	for (const next of graph[current]) {
	if (visited[next] === -1) {
	queue.enqueue(next);
	visited[next] = visited[current] + 1;
	}
	}
	}
	return visited[n] >= 1 && visited[n] <= k ? 'YES' : 'NO';
	}
	// 테스트
	console.log(
	solution(6, 6, 2, [
	[1, 4],
	[4, 2],
	[2, 6],
	[4, 3],
	[1, 2],
	[3, 1],
	])
	); // YES
	console.log(
	solution(6, 6, 2, [
	[1, 2],
	[2, 3],
	[3, 4],
	[3, 5],
	[5, 6],
	[5, 2],
	])
	); // NO
	console.log(solution(3, 3, 1, [[1, 2]])); // NO

view raw solution.js hosted with ❤ by GitHub

그래프 BFS(너비우선탐색) 문제입니다. 인접 리스트 그래프를 구현하기 위해 2차원 배열 graph를 선언하고 엣지 정보를 추가했습니다. 각 행은 시작 노드를 의미하며 끝 노드의 번호를 행 배열에 추가합니다. 

 

큐로 BFS를 구현했는데 별도의 큐 클래스를 만들어 성능이 좋지 않은 배열 메서드 shift()를 사용하지 않도록 했습니다. 통과하는 다리(엣지)가 k개 이하인 경로가 있는지 확인하는 문제이므로 1차원 배열 visited에 다리를 이용한 횟수를 저장합니다. 1번 노드부터 방문하며 처음 방문한 노드인 경우 큐에 해당 노드를 추가하고, 이전에 방문한 노드의 다리 이용 횟수 + 1을 현재 노드의 다리 이용 횟수에 저장합니다.

 

모든 경우를 탐색한 후 visited의 원소 중 k 이하인 원소가 하나라도 있으면 YES를, 모두 k보다 크면 NO를 리턴합니다.

 

 

 

 

 

 

 

 

궁금한 점이나 잘못된 점은 댓글로 남겨주시면 감사하겠습니다 :)