[JavaScript] 구름톤 챌린지 3주차 코딩테스트 : 발전기 (2)

📌  문제

📌  입력

📌  출력 및 예제

---

📌  풀이

알아야 하는 것

• Map 객체

구할 것

• 데이터 가공
  • 입력값 첫 줄에서 한 변의 길이를 scale, 단지의 기준을 standard로 잡아주고 나머지 입력값을 village로 잡아준다.
  • 건물의 유형 번호 complex와 단지를 이룬 개수를 키와 밸류로 사용하기 위해 객체 count를 선언한다.
  • 방문 여부를 확인할 visited 배열을 만든다.
  • bfs를 실행할 queue 배열을 만든다.
• 2중 for문으로 마을을 돌면서 bfs(i, j, village[i][j])를 시작한다.
  • queue 배열에서 [i, j]를 push하고 방문 처리를 한다. 동일한 건물 갯수를 계산할 sum을 0으로 초기화한다.
  • while문을 돌면서 현재 i, j를 기준으로 상하좌우를 계산하고 방문하지 않았으면서 해당 부분이 complex와 동일하다면 queue에 넣어주고 방문처리를 한다. 
  • 동일한 건물의 갯수를 증가시키고 이 갯수가 standard보다 크거나 같다면 단지를 이룰 수 있다. 따라서 count[complex]를 증가시키거나 count에 없을 경우 1로 초기화 해준다.
• count를 보면 건물 유형 번호 별로 몇 개의 단지가 있는지 확인할 수 있다.
  • 이 때 maxFrequency = 0, mostFrequentComplex를 빈 배열로 초기화한다.
  • count를 순회하면서 count[complex]가 maxFrequency보다 크거나, maxFrequency와 동일하지만 [complex], 즉 건물 유형의 번호가 지금의 건물 유형의 번호보다 큰 경우로 계속 갱신해준다.
  • 이 부분은 가장 많은 단지를 찾는 것과, 단지의 개수가 동일하다면 complex가 더 큰 건물을 찾는 부분이다.
  • 객체의 키라서 string이기 때문에 Number로 바꿔준다.

const readline = require('readline');
let rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});
let input = [];
rl.on('line', (line) => {
	input.push(line);
	if (input.length === Number(input[0].split(" ")[0])+1) {
		rl.close();
	}
});
rl.on('close', () => {
	let [scale, standard] = input.shift().split(" ").map(Number)
	let village

 = input.map((v) => v.split(" ").map(Number))
	let count = {};
	let visited = Array.from(Array(scale), () => Array(scale).fill(false))
	
	let queue = [];
	function bfs(row, col, complex) {
		queue.push([row, col]);
		visited[row][col] = true;
		let sum = 0;
		
		while (queue.length) {
			const [curR, curC] = queue.shift();
			const dir = [[0, -1], [0, 1], [-1, 0], [1, 0]];
			
			for (let i = 0; i < 4; i++) {
				const nr = curR + dir[i][0];
				const nc = curC + dir[i][1];
				
				if (nr >= 0 && nc >= 0 && nr < scale && nc < scale && !visited[nr][nc]  && village

[nr][nc] === complex) {
					queue.push([nr, nc]);
					visited[nr][nc] = true;
				}
			} sum++
		} 
		if (sum >= standard) {
			if (count[complex]) {
				count[complex]++;
			} else {
				count[complex] = 1;
			}
		}
	}
	
	for (let i = 0; i < scale; i++) {
		for (let j = 0; j < scale; j++) {
			bfs(i, j, village

[i][j])
		}
	}
	
	let maxFrequency = 0;
	let mostFrequentComplex = [];
	
	for (let complex in count) {
		if (count[complex] > maxFrequency || (count[complex] === maxFrequency && [complex] > mostFrequentComplex)) {
			maxFrequency = count[complex];
			mostFrequentComplex = [complex]
		} 
	}
	
	console.log(Number(mostFrequentComplex))
	
})

 

객체로 풀었는데 좀 복잡한 것 같아서 오늘 Map 객체로 다시 풀었다.

이 과정에서 마지막 for in 구문을 제대로 반영하지 못해 한참을 헤맸다 ㅠㅠ...

 

Map 객체로 푸는 것도 원리 자체는 동일하다.

• sum >= standard일 때 map에서 complex 키가 있는지 확인하고 있으면 기존 값에서 1을 더한 것으로 set 해주고, 없으면 set으로 complex 키에 1을 설정해준다.

이 부분만 다르고 나머지는 똑같다.

한참 힘들었던 부분이 v >= max를 걸어놓고 못 찾았던 거였다.

문제도 너무 대충 읽고... 문해력이 떨어지는 걸까? ㅎㅎㅠㅠ

 

const readline = require('readline');
let rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
let input = [];
rl.on('line', (line) => {
    input.push(line);
    if (input.length === Number(input[0].split(" ")[0]) + 1) {
        rl.close();
    }
});
rl.on('close', () => {
    let [scale, standard] = input.shift().split(" ").map(Number);
    let vilage = input.map((v) => v.split(" ").map(Number));
    let map = new Map();
    let visited = Array.from(Array(scale), () => Array(scale).fill(false));

    let queue = [];
    function bfs(row, col, complex) {
        queue.push([row, col]);
        visited[row][col] = true;
        let sum = 0;

        while (queue.length) {
            const [curR, curC] = queue.shift();
            const dir = [[0, -1], [0, 1], [-1, 0], [1, 0]];

            for (let i = 0; i < 4; i++) {
                const nr = curR + dir[i][0];
                const nc = curC + dir[i][1];

                if (nr >= 0 && nc >= 0 && nr < scale && nc < scale && !visited[nr][nc] && vilage[nr][nc] === complex) {
                    queue.push([nr, nc]);
                    visited[nr][nc] = true;
                }
            } sum++
        }
        if (sum >= standard) {
            if (map.has(complex)) {
                map.set(complex, map.get(complex)+1);
            } else {
                map.set(complex, 1)
            }
        }
    }

    for (let i = 0; i < scale; i++) {
        for (let j = 0; j < scale; j++) {
            bfs(i, j, vilage[i][j])
        }
    }

    let max = 0;
    let maxComplex = 0;

    for (let [k, v] of map) {
        if (v > max || (v === max && k > maxComplex)) {
            max = v;
            maxComplex = k;
        }
    }

    console.log(maxComplex);
});