BOJ 1343 - 폴리오미노

문제

BOJ 1343 - 폴리오미노

'X'와 '.'으로 이루어진 보드에서 'X'를 "AAAA" 또는 "BB"로 덮을 수 있을 때, 'A'를 최대한 많이 사용하여 덮어라. 불가능하면 -1을 출력한다.

입력

'X'와 '.'으로 이루어진 문자열이 주어진다 (길이 최대 50).

출력

결과 문자열 또는 -1을 출력한다.

예제

풀이

문자열 치환으로 4개 연속 X를 먼저 AAAA로, 2개 연속 X를 BB로 변환한다.

1. replaceAll("XXXX", "AAAA")로 4개짜리를 먼저 처리한다
2. replaceAll("XX", "BB")로 남은 2개짜리를 처리한다
3. 치환 후에도 X가 남아 있으면 홀수 개 연속이므로 -1을 출력한다

핵심 아이디어: 4개짜리를 먼저 치환하면 A를 최대한 사용하는 그리디가 보장되고, 남은 X가 있으면 불가능한 경우이다.

코드

package day749;
 
import java.io.*;
 
public class Day718BOJ1343폴리오미노 {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    str = str.replaceAll("XXXX", "AAAA");
    str = str.replaceAll("XX", "BB");
    System.out.println(str.contains("X") ? -1 : str);
  }
}

복잡도

• 시간: O(N)
• 공간: O(N)