[JS][백준]21608_상어 초등학교

문제 번호

21608번: 상어 초등학교

 

 

알고리즘 분류

구현

 

문제 풀이

 문제에서 시키는대로 구현해서 자리를 배치하고 완료된 배치를 갖고 학생들의 만족도를 구하면된다. 특별한 알고리즘은 없다. 

 구현문제를 풀때 배열에 객체를 넣어서 사용하는 경우가 많은것 같다. 구현문제는 코드의 길이가 다른 문제들에 비해서 긴 경우가 많음으로 차분하게 단계별로 테스트하면서 푸는것이 좋은것 같다.

 

학생 한명씩 1,2,3 단계를 거치면서 자리를 배정하는 방법으로 문제를 해결했다.

 

map 배열을 생성하여 각 학생들이 선호하는 친구들의 위치에 따른 각 자리의 점수를 매겼다.

학생 A 가 선호하는 친구가 1 이라면 

0 0 0

0 1 0

0 0 0

일때 map 배열은 1을 중심으로 상,하,좌,우에 1점을 추가한다.

0 1 0

1 0 1

0 1 0

이렇게 학생 A가 선호하는 친구들을 모두 검사하여 map 배열에 점수를 매긴다. 이를 통해 1단계를 해결 할 수 있다. 해당 과정을 진행하면서 가장 높은 점수를 기록한다.(max) 

 max와 같은 점수를 갖은 자리가 여러개일 경우 candidate 배열에 추가하여 2단계로 넘어간다.\

2단계는 candidate 배열에서 받은 x,y 좌표를 이용하여 주변에 몇개의 빈자리가 있는지 empty 프로퍼티에 저장한다.

3단계는 문제에서 요구하는대로 정렬하면 된다.

 

전체코드

const fs = require('fs');
const input = fs.readFileSync('상어 초등학교/input.txt').toString().split('\n');
const N = Number(input.shift());
let student = [];
let candidate = [];

let map = new Array(N + 2);
for (let i = 0; i < map.length; i++) {
  map[i] = new Array(N + 2).fill(0);
}

let answer = new Array(N + 2);
for (let i = 0; i < answer.length; i++) {
  answer[i] = new Array(N + 2).fill(0);
}

for (let i = 0; i <= N + 1; i++) {
  answer[i][0] = answer[i][N + 1] = answer[0][i] = answer[N + 1][i] = Infinity;
  map[i][0] = map[i][N + 1] = map[0][i] = map[N + 1][i] = Infinity;
}

for (let i = 0; i < N ** 2; i++) {
  let temp = input.shift().split(' ');
  student[i] = {
    'number': Number(temp.shift()),
    'like': temp.map(x => parseInt(x))
  }
}

/////////////////////////////////////////

for (let th = 0; th < student.length; th++) {
  // 초기화
  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= N; j++) {
      map[i][j] = 0;
    }
  }
  candidate = [];

  //  step 1.
  let max = 0;
  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= N; j++) {
      

      if (answer[i][j] == student[th].like[0] || answer[i][j] == student[th].like[1] || answer[i][j] == student[th].like[2] || answer[i][j] == student[th].like[3]) {
        // 상        
        if (answer[i - 1][j] === 0 && ++map[i - 1][j] > max)
          max = map[i - 1][j];
        // 하        
        if (answer[i + 1][j] === 0 && ++map[i + 1][j] > max)
          max = map[i + 1][j];
        // 좌
        if (answer[i][j - 1] === 0 && ++map[i][j - 1] > max)
          max = map[i][j - 1];
        // 우
        if (answer[i][j + 1] === 0 && ++map[i][j + 1] > max)
          max = map[i][j + 1];
      }
    }
  }

  for (let i = 1; i <= N; i++) {
    for (let j = 1; j <= N; j++) {
      if (map[i][j] === max && answer[i][j] === 0)
        candidate.push({
          'empty': 0,
          'x': j,
          'y': i
        });
    }
  }  
  if (candidate.length === 1) {
    let x = candidate[0].x;
    let y = candidate[0].y;
    answer[y][x] = Number(student[th].number);
    //console.log('step1');
    continue;
  }
  // step 2.
  max = 0;

  for (let i = 0; i < candidate.length; i++) {
    let x = candidate[i].x;
    let y = candidate[i].y;

    if (answer[y - 1][x] === 0)
      candidate[i].empty++;
    if (answer[y + 1][x] === 0)
      candidate[i].empty++;
    if (answer[y][x - 1] === 0)
      candidate[i].empty++;
    if (answer[y][x + 1] === 0)
      candidate[i].empty++;

    if (candidate[i].empty > max)
      max = candidate[i].empty;      
  }
  candidate = candidate.filter(candidate => candidate.empty >= max);
 
  if (candidate.length === 1) {
    let x = candidate[0].x;
    let y = candidate[0].y;
    answer[y][x] = Number(student[th].number);
    //console.log('step2');
    continue;
  }

  //step 3.
  candidate.sort((a, b) => {
    let A = a.y;
    let B = b.y;
    if (A < B) return -1;
    else if (A > B) return 1;
    else {
      A = a.x;
      B = b.x;
      if (A < B) return -1;
      else if (A > B) return 1;
      else return 0;
    }
  })  
  let x = candidate[0].x;
  let y = candidate[0].y;  
  answer[y][x] = Number(student[th].number);  
  //console.log('step3');
}

// 학생 만족도.
let totalScore = 0;
for(let i=1; i<=N; i++){
  for(let j=1; j<=N; j++){
    let score = 0;
    for(let k=0; k<student.length; k++){
      if(answer[i][j] === student[k].number){    
        if(student[k].like.findIndex(x => x === answer[i-1][j]) !== -1)
          score++;
        if(student[k].like.findIndex(x => x === answer[i+1][j]) !== -1)
          score++;
        if(student[k].like.findIndex(x => x === answer[i][j+1]) !== -1)
          score++;
        if(student[k].like.findIndex(x => x === answer[i][j-1]) !== -1)
          score++;
      }
    }
    if(score === 1)
      totalScore += 1;
    else if(score === 2)
      totalScore += 10;
    else if(score === 3)
      totalScore += 100;
    else if(score === 4)
      totalScore += 1000;
  }  
}

console.log(totalScore);

특이사항