[백준] 폴리오미노 java - greedy

민식이는 다음과 같은 폴리오미노 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

 

내 풀이

import java.io.;
import java.util.;

public class Main {
public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    String arr = br.readLine();
    String result = "";
    boolean flag = false;

    int length = 0;
    for(int i=0;i<arr.length();i++){
        if(arr.charAt(i)=='.'){
            if(length == 0){
                result += ".";
            }
            else {
                if(length%4==0){
                    for(int j=0;j<length/4;j++){
                        result += "AAAA";
                    }
                }else if(length%2==0 && length>=6){
                    int j;
                    for(j=0;j<length/4;j++){
                        result += "AAAA";
                    }
                    for(int k=0;k<(length-4*j)/2;k++){
                        result += "BB";
                    }
                }else if(length%2==0){
                    for(int j=0;j<length/2;j++){
                        result += "BB";
                    }
                } else {
                    flag = true;
                    break;
                }
                result += ".";
            }
            length=0;
        }
        else{
            length++;
        }
    }

    if(length>0){
        if(length%4==0){
            for(int j=0;j<length/4;j++){
                result += "AAAA";
            }
        }else if(length%2==0 && length>=6){
            int j;
            for(j=0;j<length/4;j++){
                result += "AAAA";
            }
            for(int k=0;k<(length-4*j)/2;k++){
                result += "BB";
            }
        }else if(length%2==0){
            for(int j=0;j<length/2;j++){
                result += "BB";
            }
        } else {
            flag = true;
        }
    }
    if(flag){
        System.out.println(-1);
    }else {
        System.out.println(result);
    }
}

 

다른 사람 풀이

import java.util.*;

public class Main {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();

        String res = "";

        res = poliomino(s);

        System.out.println(res);
    }

    private static String poliomino(String s) {
        String ans = "";
        String A = "AAAA", B = "BB";

        s = s.replaceAll("XXXX", A);
        ans = s.replaceAll("XX", B);

        if(ans.contains("X")) {
            ans = "-1";
        }

        return ans;
    }

 

 

 

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