[js, node.js]백준 2578:빙고

문제 요약

백준 2578:빙고

• 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 빈 칸을 사이에 두고 주어진다.
• 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 빈 칸을 사이에 두고 주어진다.
• 빙고판에 쓰여진 수와 사회자가 부르는 수는 각각 1부터 25까지의 수가 한 번씩 사용된다.

입력

11 12 2 24 10
16 1 13 3 25
6 20 5 21 17
19 4 8 14 9
22 15 7 23 18
5 10 7 16 2
4 22 8 17 13
3 18 1 6 25
12 19 23 14 21
11 24 9 20 15

출력

15

문제 분석

• 빙고를 판단할 기준이 되는 데이터를 어떻게 설계할 것인가?
• 각각 내 빙고 아이템(첫번째 줄~ 다섯번째 줄) 좌표를 어떻게할 것인가?
• 중복처리가 될 수 있을 것 같으니 이 점도 고민해봐야한다.
• 시간 복잡도가 차칫하면 커질 수 있으니 어떻게 로직을 분리할 것인가

문제 설계

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const obj = {};
const line = input.map((nums) => nums.split(' ').map(Number));

const half = line.length / 2;
const firstArr = line.splice(0, half); 
const callNumbers = line.splice(-half).flatMap((item) => item); 

for (let row = 0; row < 5; row++) {
  for (let col = 0; col < 5; col++) {
    const key = firstArr[row][col];
    obj[key] = [row, col];
  }
}

const rowArr = Array(5).fill(0);
const colArr = Array(5).fill(0);
const rowCompleted = Array(5).fill(false);
const colCompleted = Array(5).fill(false);
let diagonalLeft = 0;
let diagonalRight = 0;
let diagonalLeftCompleted = false;
let diagonalRightCompleted = false;
let count = 0;

for (let i = 0; i < callNumbers.length; i++) {
  const luckNumber = callNumbers[i];

  if (!(luckNumber in obj)) continue;

  const [row, col] = obj[luckNumber];

  rowArr[row]++;
  colArr[col]++;

  if (row === col) {
    diagonalLeft++;
  }

  if (row + col === 4) {
    diagonalRight++;
  }


  if (rowArr[row] === 5 && !rowCompleted[row]) {
    count++;
    rowCompleted[row] = true;
  }

  
  if (colArr[col] === 5 && !colCompleted[col]) {
    count++;
    colCompleted[col] = true;
  }


  if (diagonalLeft === 5 && !diagonalLeftCompleted) {
    count++;
    diagonalLeftCompleted = true;
  }


  if (diagonalRight === 5 && !diagonalRightCompleted) {
    count++;
    diagonalRightCompleted = true;
  }

  if (count >= 3) {
    console.log(i + 1);
    break;
  }
}

내 빙고, 사회자 빙고를 분리하는 로직 map, splice, flatMap

• 문자열로 정리하면 출력테스트를 했을 때 문자열이 쪼개지는 경우가 있었다. 예외처리를 위해 숫자로 바꿔준다.
• 사회자가 부를 숫자는 하나씩 부를 것이니 일차원 배열로 만들어준다.

const line = input.map((nums) => nums.split(' ').map(Number));

const half = line.length / 2;
const firstArr = line.splice(0, half); // 내 빙고판
const callNumbers = line.splice(-half).flatMap((item) => item);

내 빙고의 좌표를 정리하는 로직 for 문

• 좌표값을 추가한다. 내 빙고 첫번째 숫자부터 [0,0]로 시작하는 것이다.
• key값에 해당 숫자, value에 좌표값을 배열로 담는다.

const obj = {};
//...

for (let row = 0; row < 5; row++) {
  for (let col = 0; col < 5; col++) {
    const key = firstArr[row][col];
    obj[key] = [row, col];
  }
}

그러면 아래와 같은 꼴로 담긴다.

빙고를 판단하는 로직 for,Array(n).fill(k)

빙고가 되는 조건을 정리해보자.핵심은 일차원 배열로 보는 것이다.
빙고 한 줄(5개 숫자)를 1로 보았을 때

• 가로줄 5개 ➡️ Array(5).fill(0)
• 세로줄 5개 ➡️ Array(5).fill(0)
• 좌측에서 시작하는 대각선 줄 1개 ➡️ 대각A = 0
• 우측에서 시작하면 대각선 줄 1개 ➡️ 대각B = 0

인데, 이를 일차원 배열로 정리를 하는것이다.
가로줄 기준(세로줄 동일)으로 보자면 [0,0,0,0,0]가 초기값일 것이다.
예를 들어 사회자가 11,12,2,24,10을 연속적으로 불렀다고 가정해보자

사회자: 번호 11!
나: [1,0,0,0,0]

사회자: 번호 12!
나:[2,0,0,0,0]

이런식으로 해당 줄에서 일치하는 숫자가 계속 불러지니 결국 5번째 숫자에 0번째 인덱스의 값이 5가 될 것이고 이게 원빙고라는 것이다!

그럼 이를 로직에 적용해보자. 로직별로 주석을 달아놨다!

const rowArr = Array(5).fill(0);
const colArr = Array(5).fill(0);
const rowCompleted = Array(5).fill(false);
const colCompleted = Array(5).fill(false);
let diagonalLeft = 0;
let diagonalRight = 0;
let diagonalLeftCompleted = false;
let diagonalRightCompleted = false;
let count = 0;

for (let i = 0; i < callNumbers.length; i++) {
  const luckNumber = callNumbers[i];

  // 숫자가 빙고판에 있는지 확인
  if (!(luckNumber in obj)) continue;

  const [row, col] = obj[luckNumber]; // 사회자가 하나씩 불러줄 테니 그렇게 만들어 봅시다.

  rowArr[row]++;
  colArr[col]++;

  if (row === col) {
    diagonalLeft++;
  }

  if (row + col === 4) {
    diagonalRight++;
  }

  // 행 빙고 체크
  if (rowArr[row] === 5 && !rowCompleted[row]) {
    count++;
    rowCompleted[row] = true;
  }

  // 열 빙고 체크
  if (colArr[col] === 5 && !colCompleted[col]) {
    count++;
    colCompleted[col] = true;
  }

  // 대각선 왼쪽 빙고 체크
  if (diagonalLeft === 5 && !diagonalLeftCompleted) {
    count++;
    diagonalLeftCompleted = true;
  }

  // 대각선 오른쪽 빙고 체크
  if (diagonalRight === 5 && !diagonalRightCompleted) {
    count++;
    diagonalRightCompleted = true;
  }

  // 3개의 빙고가 완성되면 출력
  if (count >= 3) {
    console.log(i + 1);
    break;
  }
}

주의해야할 점은

• 중복 방지 플래그를 추가해야한다.
  rowCompleted, colCompleted 배열과 diagonalLeftCompleted, diagonalRightCompleted 플래그를 사용해 이미 확인된 행, 열, 대각선의 빙고를 다시 카운트하지 않는 로직을 세워줘야한다.
• 빙고가 한 번에 여러 개 성립할 가능이 있으므로
  ===3 을 빙고 조건을 걸면 한계가 있다.>=3로 해줘야한다.

결론

• 초반에 중복 플래그 세우지않아 카운트가 제대로 되지 않았다.
• 빙고가 되는 조건을 제한을 해버려서 예외 상황이 생겼다.
• 시간 복잡도는 $𝑂(1)$