[백준] 1343번 - 폴리오미노 (nodejs)

문제

1343번: 폴리오미노

 

민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB

이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다.

폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

입력
첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다.

출력
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

 

 

풀이

검색해보면 replace를 이용해 푼 풀이가 많이 보인다.

하지만 문제의 카테고리가 그리디인 만큼 취지에 맞는 방식으로 풀어보았다.

 

먼저 블럭은 'AAAA' 네 개 짜리와 'BB' 두 개짜리 블럭으로 이루어져 있다.

연속된 X가 홀수인지, 짝수이면 4로 나누어 몫이 몇개고 나머지가 2인지를 이용해 -1 반환 여부와 AAAA와 BB가 몇 개 필요한지 정할 수 있을 것이다.

 

for문으로 검사해서 str[i]번째 문자열이

1) X라면 count++

2) 점을 만나면

- count가 홀수라면 return -1

- 이전까지 셌던 count를 4로 나눈 몫을 구하고 그만큼 AAAA를 repeat,
  4로 나눈 나머지가 2라면 BB를 추가, 마지막으로 점을 더하고, 최종 문자열을 result 배열에 push

- count = 0으로 초기화

 

마무리로 .을 못만나고 count를 센 채로 끝났을 때를 대비해 for문 바깥에서도 같은 작업을 해준다.

 

그리고 result를 join해서 출력

 

💻 코드

const fs = require('fs');
const str = fs.readFileSync('./input.txt').toString().trim();

function solution() {
  const result = [];
  let count = 0;

  for (let i = 0; i < str.length; i++) {
    if (str[i] === '.') {
      if (count % 2 !== 0) return -1;
      const Acount = Math.floor(count / 4);
      const Bcount = count % 4;
      const chunk = 'AAAA'.repeat(Acount) + 'B'.repeat(Bcount) + '.';
      result.push(chunk);
      count = 0;
    } else {
      count++;
    }
  }

  if (count % 2 !== 0) return -1;
  const Acount = Math.floor(count / 4);
  const Bcount = count % 4;
  const chunk = 'AAAA'.repeat(Acount) + 'B'.repeat(Bcount);
  result.push(chunk);

  return result.join('');
}

console.log(solution());