누울 자리를 찾아라(백준 코딩테스트 1652번, 문자열/그리디, NodeJS 풀이)

(링크)

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

 

 

문제 수준:

실버5

 

문제 요약:

영식이가 여행와서 코레스코 콘도?라는데서 잔댄다.

방은 N x N 크기의 방이다. 옮길 수 없는 짐도 있다고 한다.

영식이가 누우려면 최소 2칸 이상 이어져 있는 공간이 필요하다.

 

'이때 영식이가 무조건 몸을 쭉 피기 때문에 머리와 발은 무조건 벽이나 짐에 닿는다.

중간에 어정쩡하게 자지않는다'...라는 조건이 있는데 사실 뭔 말인지 헷갈렸다. 이 말은,

 

'5칸 연속 빈 공간이 있을 때, 최소 2칸 필요하다고 해서

5칸을 2칸씩 다 쪼개보면 4가지의 경우가 있네?' 라고 하지 않는다는 것이다.

5칸 연속 빈 공간은 그냥 1개의 경우로 보는 것이다.

 

 

이때 가로로 잘 수 있는 경우와 세로로 잘 수 있는 경우를 모두 구하시오

 

입출력 예 (입력 / 출력):

 

문제 풀이 전략:

 

예전에 풀었던 유기농 배추 문제처럼 dfs로 풀어야하나 1초 정도 고민했는데, 그럴 필요까진 없다.

2차원 문자열을 순회하며 '최소 2번 연속 빈공간이 발생하는 릴레이가 얼마나 발생하는지'를 측정하면 된다.

 

어제 제로초 자료구조 연결리스트 강의를 들으며

다음/이전 노드를 prev, current, next라는 이름으로 계속 체이닝 해놓는 방식을 연습했는데,

여기서도 'prev값을 캐싱하여 current와 비교하고, current를 다시 prev로 만들어서 다음 순회 진행하고'의 반복을 하면 될 것 같다.

 

내 풀이:

// 누울 자리를 찾아라, 1652
let fs = require("fs");
const [n, ...map] = fs.readFileSync("input.txt").toString().trim().split("\n");
// 참고로 map은 ["...X.", "..X..", ... ] 이런 식이다.

// 정답 console.log(...);
console.log(rowFinder(map), colFinder(map));

// 행에서 잘 수 있는 공간이 얼마나 있는지 확인하는 함수
function rowFinder(map) {
  let result = 0;

  for (let i = 0; i < n; i++) {
    let combo = 0; // 연속 횟수
    let prev = ""; // 전의 값

    for (let j = 0; j < n; j++) {
      const current = map[i][j]; // 현재 문자열

      if (prev === "." && current === ".") { // 전의 것과 현재 것이 모두 빈공간이면
        combo++; // 콤보 플러스
        if (j === n - 1) { // prev와 current 모두 빈 공간이어도 마지막 행 또는 열이었으면 연속콤보 끊기
          result++; // 결과는 1 더해주고,
          combo = 0; // 콤보는 초기화
        }
      } else {
        if (combo > 0) { // 막힌 공간이지만 콤보가 발생했었을 시
          result++; // 결과는 1 더해주고,
          combo = 0; // 콤보는 초기화
        }
      }
      prev = map[i][j]; // 위 처리를 다 해줬으면 prev는 current로 변경
    }
  }

  return result; // result를 반환
}

// 열에서 잘 수 있는 공간이 얼마나 있는지 확인하는 함수 (위와 똑같은 로직이다.)
// 위와 똑같은 로직이지만 순회를 열 방향으로 하게 만든 함수이다.
function colFinder(map) {
  let result = 0;

  for (let i = 0; i < n; i++) {
    let combo = 0;
    let prev = "";

    for (let j = 0; j < n; j++) {
      const current = map[j][i]; // map[i][j]가 아니라 map[j][i]이다.

      if (prev === "." && current === ".") {
        combo++;
        if (j === n - 1) {
          result++;
          combo = 0;
        }
      } else {
        if (combo > 0) {
          result++;
          combo = 0;
        }
      }
      prev = map[j][i];
    }
  }

  return result;
}