[백준 node.js] 2599번_짝 정하기

백준 DFS 알고리즘 2599번_짝 정하기

난이도 : 실버IV

해결하지 못한 문제입니다.

 

문제 설명

입출력

 

문제 풀이 : 초등학교 출신을 순서대로 배열의 index값으로 생각하고 이차원 배열에 각각 학교별로 남자, 여자의 수를 입력 받는다. 그후 list(초등학교)를 순서대로 돌면서 자기학교를 제외한 여학생들의 수와 비교해서 쌍을 맺을수 있는대로 맺어준다. 맺은 쌍 만큼 남학생, 여학생 수를 빼주고 맺은 쌍의 수를 배열에 넣어준다.

 

이 과정을 마치고나면 list(초등학교)에는 맺을 수 있는 쌍을 제외한 값이 존재한다(모두 쌍을 맺었다면 모든 배열에 0 그렇지 않다면 0을 제외한 수가 남게 된다.)

 

그후 모든 list(초등학교)에 0만 존재한다면 모든 쌍이 맺어진것이므로 학교의 수만큼 짤라서 맺어진 쌍을 출력하면된다.

 

//실버4 짝 정하기
function solution(list) {
  //같은 학교인지 판별하기 위한 방문표시
  let visited = new Array(list.length).fill(false);
  //남 여 짝꿍이 되는 쌍
  let pair = [];
  //리스트수(초등학교 개수만큼) 반복
  for (let i = 0; i < list.length; i++) {
    //i학교의 남자 학생 인원
    let tmp = list[i][0];
    //i학교 여자 학생과는 짝꿍이 될수없으므로 방문처리
    visited[i] = true;
    for (let j = 0; j < list.length; j++) {
      //같은학교가 아니면
      if (visited[j] === false) {
        //여학생수와 남학생수에서 적은값으로 빼주면 그 만큼 짝꿍 쌍이 생긴다.
        let girl = list[j][1];
        let tmp = Math.min(girl, list[i][0]);
        //맺어진 짝꿍 쌍을 배열에 추가
        pair.push(tmp);
        //쌍을 맺은 남학생 여학생은 값을 뺴준다.
        list[i][0] -= tmp;
        list[j][1] -= tmp;
      }
    }
    //다음 학교를 위해 방문처리를 리셋
    visited[i] = false;
  }

  //
  let result = true;
  //list(학교 학생들)에 값이 남아있다면 짝이 안된 학생이 있으므로 결과값 false
  for (let i = 0; i < list.length; i++) {
    for (let j = 0; j < 2; j++) {
      if (list[i][j] !== 0) {
        result = false;
      }
    }
  }
  //위의 결과값에 따라
  //모든 학생들의 짝을 정할 수 있으면 첫 줄에 1을 출력하고, 그렇지 않으면 0을 출력한다.
  if (result) {
    console.log(1);
    //pair에 넣은 맺어진 쌍의 수를 학교당 한번에 출력하기 위해(list길이에 -1을 해준다 (배열은 0부터시작))
    for (let k = 0; k < pair.length; k += list.length - 1) {
      //list(학교 길이)만큼 잘라서 한번씩 출력
      let text = pair.slice(k, k + (list.length - 1));
      console.log(text.join(" "));
    }
  } else {
    console.log(0);
  }
}

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

let input = [];
rl.on("line", function (line) {
  //여러줄 입력
  input.push(line);
}).on("close", function () {
  //학생수
  let [n] = input[0];
  input = input.slice(1);
  let list = Array.from(Array(input.length), () => new Array(2));

  //이차원 배열에 학생들의 수를 대입
  for (let i = 0; i < input.length; i++) {
    let [x, y] = input[i].split(" ").map((el) => parseInt(el));
    list[i][0] = x;
    list[i][1] = y;
  }
  solution(list);
  process.exit();
});

 

* 일단 이 문제가 왜 DFS 분류에 포함되어있는지 모르겠다... 여튼 풀려고 문제를 선택한 만큼 풀려고했다. 여러 테스트를 거치고 제출을 했는데 어디가 문제인지 자꾸 틀렸다고 나온다. 임의로 여러 테스트 케이스를 만들어서 해봤고 다 통과했는데 제출만하면 틀렸다고 나온다. 아마 내가 생각치 못한 예외가 발생한 모양인거같아서 다른 사람들 코드를 통해 정보를 얻고자 찾아보았지만 실패했다.. 아마 문제가 특이?이상?해서 푼사람이 없나보다....

혹시 이 글을 읽고 계시고 틀린부분을 찾았다면 알려주시면 감사하겠습니다!