[백준] 1343번 : 폴리오미노

솔방울·2023년 5월 24일

코딩테스트

목록 보기

8/13

문제

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

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

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

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

입력

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

출력

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

첫 시도

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


let result = ""
let isFalse = false

input.forEach((el) => {
    const length = el.length
    if(length === 0) {
        result += "."
    } else if (length % 2 !== 0) {
        isFalse = true;
        return;
    } else {
        result += "AAAA".repeat(parseInt(length/4)) + "BB".repeat((length%4)/2) + "." 
    }
})

if(isFalse) {
  console.log(-1)
} else {
  console.log(result.slice(0,-1))
}

꽤나 쉬운 문제인 줄 알았는데, . 이 친구를 어떻게 사이에 넣어야 할지 고민이었다. split을 하면 .을 기준으로 나누지만, 이렇게 . 1개인 경우엔 split을 잘 수행하지만, .. 이렇게 .이 2개 이상인 경우 .와 . 사이에 빈 문자열인 ""이 있다고 가정한다.

예를 들어

const input = "XXXX....".split(".");
console.log(input);
// ["XXXX","","",""]

이런 셈인 것이다.

일단 input에 있는 각 문자열 데이터의 length의 경우를 나누어

0인 경우 : .을 붙인다
length가 홀수인 경우 : break 후 -1 출력
length가 짝수인 경우 : 앞에서부터 4개씩 XXXX 붙이고 나머지는 XX 붙임

이렇게 짜고, 디폴트로 length가 짝수인 경우엔 뒤에 .를 한번 더 붙여 split 메소드에서 .이 하나 상실되는 부분을 보충했다.

하지만 이 경우 마지막에는 필히 .이 추가되므로 결과값에서는 slice(0,-1)을 사용하여 마지막 문자열을 제거한 값을 출력하였다.

그러나 내가 의도한 forEach의 break은 성공적으로 작동하지 못했다. 그저 forEach의 callback에서 length가 홀수인 경우엔, isFalse만 true로 선언하고 계속 loop을 돌게 된다.

두번째 시도

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


let result = ""
let isFalse = false

input.every((el) => {
    const length = el.length
    if(length === 0) {
        result += "."
    } else if (length % 2 !== 0) {
        isFalse = true;
        return false
    } else {
        result += "AAAA".repeat(parseInt(length/4)) + "BB".repeat((length%4)/2) + "." 
    }
    return true
})

if(isFalse) {
  console.log(-1)
} else {
  console.log(result.slice(0,-1))
}

그러므로 forEach에서 break처럼 사용할 수 있는 방법을 찾다가 every라는 문법을 보게 되었다. every는 forEach와 똑같지만, falsy한 값을 return하게 되면 그 이후의 순회를 중지한다. length가 홀수인 경우에 의미없는 순회를 돌지 않고 내가 의도한 대로 바로 결과값으로 가게 된다. 이렇게 리팩토링하여 120ms가 소요되었다. (전 코드는 128ms)

참고 코드

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim();

let copyInputs = inputs;
copyInputs = copyInputs.replace(/XXXX/g,'AAAA');
copyInputs = copyInputs.replace(/XX/g,'BB');

if(copyInputs.includes('X')){
    console.log(-1)
} else {
    console.log(copyInputs)
}

다른 분의 코드인데, 아주 깔끔하게 정규표현식을 잘 사용하셨다. 나도 정규표현식 사용을 고려해봤지만, XXXX를 replace하면 정확히 XXXX, 이렇게 4개의 길이일 경우에만 바꾸는 건 아닐까 싶어 사용하지 않았다.

하지만 정규식의 구성 중 정규식 패턴 뒤에 있는 플래그에서 g라는 전역 검색을 통해 전체 문자열을 순회할 수 있으며, 위에서 우려했던, 정확히 일치하는 개수만 바꾸는 것이 아니라 앞에서부터 차례대로 바꾼다는 사실이었다. regex에 대한 공부도 차근차근 해봐야겠다.