[백준_1343번] 폴리오미노

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

1343번: 폴리오미노

[문제]

 민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB. 이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_1343 {
	static StringBuilder sb=new StringBuilder();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		String str=sc.next();
		
		int count=0;
		
		for(int i=0;i<str.length();i++) {
			if(str.charAt(i)=='.') {
				// count가 짝수라면 덮어쓸 수 있는 경우
				if(count%2==0) {
					cover(count);
					count=0;
				}
				
				// count가 홀수라면 덮어쓸 수 없는 경우이므로 -1 출력 후 종료
				else {
					System.out.println(-1);
					System.exit(0);
				}
				
				// 덮어쓰기가 끝났다면 . 추가 
				sb.append('.');
			}
			
			// X 개수 count
			else
				count++;
		}
		
		// 문자열의 끝에 X가 있는 경우 처리 
		if(count%2==0) 
			cover(count);
		else {
			System.out.println(-1);
			System.exit(0);
		}
		
		System.out.println(sb);
	}
	
	// 덮어쓰기 함수
	static void cover(int count) {
		int length=count/4;
		
		// count를 4로 나눈 몫 만큼 AAAA 덮어쓰기
		for(int i=0;i<length;i++)
			sb.append("AAAA");
		
		length=count%4;
		
		// 4로 나눠 떨어지지 않는다면 반드시 남은 count는 2이기 때문에 BB 한번 덮어쓰기
		if(length!=0)
			sb.append("BB");
	}
}

import java.util.*;

public class BaekJoon_1343 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		String str=sc.next();
		
		/*
		 * XXXX -> AAAA로 변경
		 * XX -> BB로 변경 
		 * 
		 * 사전순으로 앞서는 답을 출력해야 하기 때문에 AAAA를 먼저 치환
		 */
		str=str.replaceAll("XXXX", "AAAA");
		str=str.replaceAll("XX", "BB");
		
		
		// 위의 과정을 수행 후에도 X가 남아있다면 덮을 수 없는 문자열
		if(str.contains("X"))
			System.out.println(-1);
		else
			System.out.println(str);
	}

}

 

[고찰]

 이번 문제를 처음에 시도했을 때는 문자열을 처음부터 탐색하면서 X인 경우 count를 하고, .를 만난다면 여태까지 누적된 X의 개수로 처리를 하려고 했는데 생각했던 것 만큼 잘 되지 않아 다른 사람의 코드를 참고하였다. 여러 글들을 보는데 두 번째 코드처럼 replaeAll() 함수를 사용하여 아주 간단하게 문제를 해결한 분은 보고 놀랐다.  

 함수를 사용하지 않고 직접 구현할 수도 있다. 여기서 핵심은 X의 개수가 짝수이고 4로 나눠 떨어지지 않는 경우에는 나머지가 무조건 2라는 사실이다. 따라서 X의 개수가 홀수인 경우에는 -1을 출력하고 프로그램을 종료하지만, 짝수인 경우에는 X의 개수를 4로 나눈 몫 만큼 "AAAA"를 붙여주고, 나머지가 있는 경우에는 "BB"를 한번 붙여주면 된다는 것이다. 

이번 문제도 그리디 문제였는데 그리디 문제는 출제 형식이 다양하다 보니 문제를 보고 어떻게 구현할 것인지 아이디어를 떠올리는 것이 굉장히 중요한 것 같다. 한 문제를 풀더라도 스스로 해결방법을 끝까지 고민해보는 습관을 길러야 할 것 같다.