[백준] [1343] 폴리오미노 (그리디) (JAVA)

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

1343번: 폴리오미노

---

문제

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

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

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

입력

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

출력

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

예제 입력 1 복사

XXXXXX

예제 출력 1 복사

AAAABB

예제 입력 2 복사

XX.XX

예제 출력 2 복사

BB.BB

예제 입력 3 복사

XXXX....XXX.....XX

예제 출력 3 복사

-1

예제 입력 4 복사

X

예제 출력 4 복사

-1

예제 입력 5 복사

XX.XXXXXXXXXX..XXXXXXXX...XXXXXX

예제 출력 5 복사

BB.AAAAAAAABB..AAAAAAAA...AAAABB

---

※ JAVA 코드 (폴리오미노)

import java.io.*;

public class Main {
	
	static String P1 = "AAAA";
	static String P2 = "BB";
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		// 입력 문자열
		String str = br.readLine();
		StringBuilder sb = new StringBuilder();
		
		int cnt = 0;
		
		for(int i = 0; i < str.length(); i++) {
			if(str.charAt(i) == '.') {
				sb.append(".");
				cnt = 0;
			} else {
				cnt++;
				
				if(cnt == 4) {
					sb.append(P1);
					cnt = 0;
				} else if(cnt == 2) {
					if(i == str.length() - 1 || str.charAt(i + 1) == '.') {
						sb.append(P2);
						cnt = 0;
					}
				}
			}
		}
		
		if(sb.length() != str.length()) {
			System.out.println("-1");
		} else {
			System.out.println(sb.toString());
		}
	}
}

---

※ 생각정리 (폴리오미노)
폴리오미노 문제를 해결하기 위해 몇가지 생각해야할 것들이 있다.
XX일때 뒤에 있는 값에 따라 XXXX가 될 수 있고 혹은 XX가 될 수 있다.
XX.일때는 BB.를 출력해야하며 XXXX.일때는 AAAA.가 출력되야한다.
1. 변수 str에 문자열을 입력받고 문자열길이 끝까지 반복해서 문자를 입력받는다.
2. 현재 문자가 X라면 cnt를 증가시켜 문자의 개수를 센다.
3. 현재 문자가 '.' 이라면 개수를 '.'을 sb에 추가한다.
4. 현재 문자가 X일때 cnt의 개수를 증가시키고 cnt가 4라면 "AAAA'를 sb에 추가한다.
5. 현재 문자가 X일때 cnt의 개수를 증가시키고 cnt가 2라면 그 뒤의 값이 없는지 혹은 '.'인지 확인하고 맞다면 "BB"를 추가한다.
 
-새벽코딩-