[백준-그리디] 폴리오미노 (Java)

문제

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

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

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

제한 조건

• 제한 시간 : 2초
• 풀이 시간 : 30분

입력

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

출력

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

예시

입력	출력
XXXXXX	AAAABB
XX.XX	BB.BB
XXXX....XXX.....XX	-1
X	-1
XX.XXXXXXXXXX..XXXXXXXX...XXXXXX	BB.AAAAAAAABB..AAAAAAAA...AAAABB

풀이

이 문제는 연속된 X의 개수를 체크하며 보드판을 만들어나가면 된다. 다만 문제에 제시된 것처럼
폴리오미노를 사전 순으로 덮아야 한다는 조건을 지켜야 한다.

'X'가 나왔을 경우에는 '.'이 나오거나 종료될 때까지 X의 개수를 체크한다.
'.'이 나왔을 때는 'X'의 개수가 0일 경우와 0이상일 경우 2가지로 나눠서 진행한다.

if (0 이상일 경우):
    'X'의 개수를 4로 나눈 몫만큼 A를 보드판에 추가 # A로 덮을 수 있는 개수
  
    if ('X'의 개수를 4로 나눈 나머지가 2나 0이 아닐 경우): 
        폴리오미노로 다 덮을 수 없는 문자열이므로 -1을 출력
    else:
        나머지만큼 B를 보드판에 추가 # 2면 B로 한번 덮을 수 있고, 0이면 B로 덮을 것이 없음
    
else: 
    '.'을 보드판에 추가

이 풀이의 시간 복잡도는 O(N)이고 보드판의 최대 길이가 50이므로 풀이가 가능하다.

이슈

1. 보드판이 'X'로만 이뤄질 경우 루프가 끝나면 '.'을 체크하는 조건문을 거치지 않게 되므로 빈 보드판을 출력됨.
   • 루프가 끝난 후에도 'X'의 길이가 0 이상이면 폴리오미노로 변환하는 로직을 추가함.
2. 보드판을 출력할 때 처음 보드판 형태에서 'X'만 폴리오미노로 변환하여 출력해야 하는데, '.'이 먼저 찍힌 후 폴리오미노가 출력됨.
   • StringBuilder에 '.'을 append하는 구문을 'X' 길이를 체크하는 조건문 이후에 하도록 변경.

코드를 작성하고 나서 발생한 2가지 이슈는 사소한 부분들인데, 문제를 풀이하는데 정신이 팔려 놓치고 말았다. 수도 코드를 작성해보며 생각하지 못한 엣지 케이스가 존재하는지 확인해 볼 필요가 있다.

코드

• 코드