[Node.js] 백준 Javascript 21608 상어 초등학교

1. 문제

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

 

2. 풀이과정

이런 구현 문제는 풀기 전 설계를 완료하고 코드를 짜야한다.

- 설계

1. 입력된 순서대로 앉힌다.

2. 학생을 앉힐 때 현재 교실(board)의 모든 빈자리에 대한 인접 정보를 받아서 저장

3. 인접 정보는 해당 빈자리의 좌표, 인접 빈자리 개수, 인접 좋아하는 학생의 수를 가진다.

4. 3으로 수집한 인접 정보들을 조건에 맞게 정렬하여 특정 학생의 최적의 자리 선정

5. 해당 자리에 학생을 앉힌다.

6. 모두 앉힌 이후 조건에 따라 만족도를 조사한다.

 

- 구현 함수 설명

getSeatInfo(r, c, studentNum) : 특정 자리 좌표와 학생 번호를 매개변수로 받음

특정 자리 좌표를 기준으로 4방향 탐색 -> 빈자리 수, studentNum에 해당하는 좋아하는 학생 수 계산

 

choiceSeat( studentNum)

studentNum이 앉을 최적의 자리를 선정하여 앉힌다.

모든 자리 탐색 -> 빈자리에 대해서 getSeatInfo 수행 -> 인접 정보 배열(neighborInfos)에 저장

문제 조건

neighborInfos을 위 조건에 맞게 정렬시킨다. 정렬 후 가장 앞의 객체가 최적의 자리

neighborInfos.sort((a, b) => {
            if (a.match !== b.match) {
                return b.match - a.match; // match 기준 내림차순 정렬
            } else if (a.empty !== b.empty) {
                return b.empty - a.empty; // empty 기준 내림차순 정렬
            } else if (a.r !== b.r) {
                return a.r - b.r; // r 기준 오름차순 정렬
            } else {
                return a.c - b.c; // c 기준 오름차순 정렬
            }
        });
        board[neighborInfos[0].r][neighborInfos[0].c] = studentNum; //최적의 위치에 앉히기

 

calcSatisfy()

모든 자리에 대해서 getSeatInfo로 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 받아오고 이에 따라 만족도 처리

 

-❗주의할 점

result += Math.floor(10 ** (getSeatInfo(i, j ,board[i][j]).match-1));

만족도 처리 시에 match가 0인 경우 10의 -1승은 0.1 이므로 0으로 만들기 위해 Math.floor를 사용해야 함

 

3. 자바스크립트 정답 코드

const fs = require('fs');
const filepath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const input = fs.readFileSync(filepath).toString().trim().split('\n');
//입력 데이터 정리
const N = +input.shift();
const students = input.map(x => {
    const [num, ...likes] = x.trim().split(' ').map(Number);
    return { num, likes };
});

let board = Array.from({ length: N }, () => Array(N).fill(0)); 

const dr = [-1, 1, 0, 0];
const dc = [0, 0, -1, 1];

main();

function main(){
    for(let i=0; i< N**2; i++){
        if(i == 0){
            board[1][1] = students[i].num; //첫학생은 1,1에 무조건 앉는다.
            continue;
        }
        choiceSeat(students[i].num); //학생을 조건에 맞게 앉히기
    }
    console.log(calcSatisfy()); //모두 앉은 후 만족도 계산하기
}

// 최적의 자리 선택 및 학생 배치 함수
function choiceSeat(studentNum){
    const neighborInfos = []; //인접 자리 정보를 모으는 배열
    for(let i = 0; i<N; i++){ 
        for(let j =0; j<N; j++){
            if(board[i][j] !== 0) continue; //이미 차있는 자리 패스
            neighborInfos.push(getSeatInfo(i, j, studentNum));
            }    
        }
        neighborInfos.sort((a, b) => {
            if (a.match !== b.match) {
                return b.match - a.match; // match 기준 내림차순 정렬
            } else if (a.empty !== b.empty) {
                return b.empty - a.empty; // empty 기준 내림차순 정렬
            } else if (a.r !== b.r) {
                return a.r - b.r; // r 기준 오름차순 정렬
            } else {
                return a.c - b.c; // c 기준 오름차순 정렬
            }
        });
        board[neighborInfos[0].r][neighborInfos[0].c] = studentNum; //최적의 위치에 앉히기
}

// 특정 자리의 인접 정보 계산 함수
function getSeatInfo(r, c, studentNum){
    let empty = 0;
    let match = 0;
    // 학생 번호에 맞는 좋아하는 학생들 찾기
    let studentLikes = students.find(student => student.num === studentNum)?.likes || [];
    for(let i = 0; i< 4; i++){
        nr = r + dr[i];
        nc= c + dc[i];
        if(nr < 0 || nc < 0 || nr >= N || nc >= N) continue;
        if (board[nr][nc] == 0) empty++;
        else if(studentLikes.includes(board[nr][nc])) match++
    }
    return { r: r, c: c, empty: empty, match: match };
}

//만족도 처리
function calcSatisfy(){
    let result = 0;
    for(let i = 0; i<N; i++){ //남아있는 모든 자리의 정보를 수집
        for(let j =0; j<N; j++){
            result += Math.floor(10 ** (getSeatInfo(i, j ,board[i][j]).match-1));
            }    
        }
    return result;
}

 

4. 새로 알게 된 점

1. 자바스크립트 임의 정렬 방법

c++ 만 사용해서 Javascript에서 sort함수 사용 시 비교함수 적용법을 몰랐다.

자바 스크립트는 비교 조건에 따른 반환 값에 따라 a, b를 정렬한다.

배열.sort(비교함수);

배열.sort(function(a, b) {비교조건}); //함수사용
배열.sort((a, b) => {비교 조건}); 	//화살표 함수 사용

ex) a == 1, b == 3 a<b인 상황이라면
오름차순 정렬 
return a - b; (음수 반환)

내림차순 정렬
return b - a; (양수 반환)

반환 값이 음수라면 a를 앞에 정렬

반환 값이 양수라면 b를 앞에 정렬 

 

2. 2차원 배열 초기화 시키기

let board = Array.from({ length: N }, () => Array(N).fill(0));

from 메서드로 N * N로 원소가 모두 0인 2차원 배열로 초기화시킬 수 있다.