백준 20125 - 쿠키의 신체 측정

문제

이번에는 Node 로 한번 달려보기로.

쿠키 해부학

쿠키의 신체는 머리, 심장, 허리, 그리고 좌우 팔, 다리로 구성되어 있다.

그림에서 빨간 곳으로 칠해진 부분이 심장이다. 머리는 심장 바로 윗 칸에 1칸 크기로 있다. <- 머리 아래가 심장

왼쪽 팔은 심장 바로 왼쪽에 붙어있고 왼쪽으로 뻗어 있으며, 오른쪽 팔은 심장 바로 오른쪽에 붙어있고 오른쪽으로 뻗어있다.

허리는 심장의 바로 아래 쪽에 붙어있고 아래 쪽으로 뻗어 있다.

왼쪽 다리는 허리의 왼쪽 아래에, 오른쪽 다리는 허리의 오른쪽 아래에 바로 붙어있고, 각 다리들은 전부 아래쪽으로 뻗어 있다.

각 신체 부위들은 절대로 끊겨있지 않으며 굽혀진 곳도 없다. 또한, 허리, 팔, 다리의 길이는 1 이상이며, 너비는 무조건 1이다.

접근

  1. 머리를 찾는다. - 심장 위치 파악하기
for (let r = 0; r < N; r++) {
  for (let c = 0; c < N; c++) {
    if (cookieBody[r][c] === "*") {
      heartR = r + 1;
      heartC = c;
      break;
    }
  }
  if (heartR !== undefined) break;
}
  1. 심장의 왼쪽은 왼팔, 오른쪽은 오른팔이라는 사실을 이용해 팔의 길이를 측정한다.
let leftArm = 0;
for (let c = heartC - 1; c >= 0; c--) {
  if (cookieBody[heartR][c] === "*") {
    leftArm++;
  } else {
    break;
  }
}

let rightArm = 0;
for (let c = heartC + 1; c < N; c++) {
  if (cookieBody[heartR][c] === "*") {
    rightArm++;
  } else {
    break;
  }
}
  1. 허리는 심장의 아래이므로 허리의 길이를 측정한다. (허리가 끝나는 부분은 - 가 입력되어있어 편함)
let waist = 0;
let waistEndR = heartR;
for (let r = heartR + 1; r < N; r++) {
  if (cookieBody[r][heartC] === "*") {
    waist++;
    waistEndR = r;
  } else {
    break;
  }
}
  1. 허리(심장) 기준 1칸 왼쪽을 세로로 순회하여 왼다리를 측정한다.
let leftLeg = 0;
for (let r = waistEndR + 1; r < N; r++) {
  if (heartC - 1 >= 0 && cookieBody[r][heartC - 1] === "*") {
    leftLeg++;
  } else {
    break;
  }
}
  1. 허리(심장) 기준 1칸 오른쪽을 세로로 순회하여 오른다리를 측정한다.
let rightLeg = 0;
for (let r = waistEndR + 1; r < N; r++) {
  if (heartC + 1 < N && cookieBody[r][heartC + 1] === "*") {
    rightLeg++;
  } else {
    break;
  }
}

고민

이걸 for문을

for () {}
for () {}
for () {}
for () {}

이렇게 돌리는 것이 시간초과로 이어지지 않을까? 하는 고민이 있었는데…

N의 최대 크기는 100, O(N^2) 정도의 시간 복잡도!

코드

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

const N = parseInt(input[0]);
const cookieBody = input.slice(1).map((row) => row.split(""));

let heartR, heartC;

// 1. 심장 위치 찾기
for (let r = 0; r < N; r++) {
  for (let c = 0; c < N; c++) {
    if (cookieBody[r][c] === "*") {
      heartR = r + 1;
      heartC = c;
      break;
    }
  }
  if (heartR !== undefined) break;
}
// 팔

let leftArm = 0;
for (let c = heartC - 1; c >= 0; c--) {
  if (cookieBody[heartR][c] === "*") {
    leftArm++;
  } else {
    break;
  }
}

let rightArm = 0;
for (let c = heartC + 1; c < N; c++) {
  if (cookieBody[heartR][c] === "*") {
    rightArm++;
  } else {
    break;
  }
}

// 허리
let waist = 0;
let waistEndR = heartR;
for (let r = heartR + 1; r < N; r++) {
  if (cookieBody[r][heartC] === "*") {
    waist++;
    waistEndR = r;
  } else {
    break;
  }
}

// 다리 길이 측정
let leftLeg = 0;
for (let r = waistEndR + 1; r < N; r++) {
  if (heartC - 1 >= 0 && cookieBody[r][heartC - 1] === "*") {
    leftLeg++;
  } else {
    break;
  }
}

let rightLeg = 0;
for (let r = waistEndR + 1; r < N; r++) {
  if (heartC + 1 < N && cookieBody[r][heartC + 1] === "*") {
    rightLeg++;
  } else {
    break;
  }
}

console.log(heartR + 1, heartC + 1);
console.log(leftArm, rightArm, waist, leftLeg, rightLeg);

결론

이제는 쿠키의 팔다리도 측정하는 사람이 됐다.

모든 단계를 한 번에 처리하는 것 보다 단계별로 나눠서 접근하는 것이 더 편할 수 있겠다는 점을 다시 한 번 느껴버린 순간.