[Softeer] 진정한 효도 JS

https://softeer.ai/practice/7374

 

남우는 어버이날을 맞아 부모님의 일을 돕기로 하였습니다. 남우의 부모님께서는 농사를 지으시기에, 남우는 땅을 일구는 일을 도우려고 합니다.

 

 

남우에게 할당된 땅은 3 * 3 크기의 격자로 이루어져 있으며, 각 땅의 높이는 1이상 3이하의 정수값으로 이루어져 있습니다. 부모님께서 농사를 지을 땅의 크기는 1 * 3이며, 농사를 짓기 위해서는 해당 영역 내 땅의 높이가 전부 동일해야 합니다. 따라서 남우는 특정 땅의 높이를 낮추거나 높여, 3 * 3 격자 내에 부모님께서 농사를 지을 수 있는 영역이 최소 1곳 이상 생기도록 만들려고 합니다.

 

 

남우가 특정 땅의 높이를 1만큼 낮추거나 높이는데 1만큼의 비용이 소요된다고 했을 때, 부모님께서 농사를 지으실 수 있도록 땅을 일구기 위해 남우에게 필요한 최소 비용을 구하는 프로그램을 작성해보세요.

단, 1 * 3 크기의 영역은 가로, 세로로 놓이는 것이 모두 가능하기에, 3 * 3 크기의 격자에서는 땅의 높이만 동일하다면 최대 6개의 영역에 농사를 지을 수 있음에 유의합니다.

 

본 문제의 저작권은 (주) 브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금합니다.

제약조건

• 1 ≤ 땅의 높이 ≤ 3

입력형식

세 개의 줄에 걸쳐 각 행에 해당하는 땅의 높이 정보가 공백을 사이에 두고 주어집니다.

출력형식

부모님께서 농사를 짓는 것이 가능해지기 위해 남우에게 필요한 최소 비용을 출력합니다.

---

풀이

배열이3*3이므로 모든 3개의 row과 3개의 col을 모두 탐색한다

예를 들어 [1,2,2] 에서 최소로 변경하여 고르게 만들수 있는 경우를 리턴한다

 

어떻게 하면 최소변경 횟수를 알 수 있을까?

1,2,3만 넣을 수 있으므로 obj로 한 줄상 1,2,3의 갯수를 정리한다

obj의 key가 1개면 이미 고르므로 변경횟수는 0

obj의 key가 3개면 1,2,3인 경우이므로 이는 [2,2,2]로 만드는게 최소이다. 그러므로 2

obj의 key가 2개면 최소변경횟수는 Math.abs(갯수가 더 큰 key - 작은 key )이다.

예를 들어 [1,1,3]를 갯수로 정리하면  {1: 2, 3: 1} 인 경우 1개인 3을 1로 변경하는게 최소비용이 든다.

그러므로 Math.abs[1-3] = 2를 리턴하게 되는거다

 

이런식으로 모든 경우를 탐색한 뒤 최소값을 리턴한다

 

 

col대로 arr를 만드는 법

 

col은 고정되어있고, row를 순회하며 나오는 값을 넣으면 된다

const map = //
for (let c = 0; c < 3; c++) {
    const col = [];
    for (let r = 0; r < 3; r++) {
        col.push(map[r][c])
    }
   	console.log(col);
}

 

 

코드

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

const lines = [];

// input
rl.on('line', input => {
    lines.push(input.split(' ').map(e => parseInt(e)));
})

// 완전탐색 매 열, 매 행 마다 이미 고른 땅이 있는 지 확인

function getMinCost(arr) {
    const obj = {};
    for (let i = 0; i < 3; i++) {
        const currNum = arr[i];
        obj[currNum] = (obj[currNum] || 0)+1;
    }
    const keyCount = Object.keys(obj).length;
    if (keyCount === 1) return 0;
    if (keyCount === 3) return 2; // 1,2,3인경우
    const sortableArr = []; 
    for (const [key, value] of Object.entries(obj)) {
        sortableArr.push({key, value});
    }
    sortableArr.sort((a, b) => a.value - b.value);
    return Math.abs(sortableArr[1].key - sortableArr[0].key);
}
rl.on('close', () => {
    let answer = Infinity;
 
    // check row
    for (let r = 0; r < 3; r++) {
        const row = lines[r];
        answer = Math.min(answer, getMinCost(row));
    }
    // check col
    for (let c = 0; c < 3; c++) {
        const col = [];
        for (let r = 0; r < 3; r++) {
            col.push(lines[r][c])
        }
        answer = Math.min(answer, getMinCost(col))
    }
    console.log(answer);
    process.exit();
})