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

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

1343번: 폴리오미노

📚 문제

'.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 AAAA와 BB 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.

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

 

📝 문제 해결

입력받은 문자열을 split() 함수를 사용해 . 를 기준으로 잘라 배열에 넣어준 뒤

만약 길이가 홀수인 원소가 있다면 -> -1을 출력
모두 짝수일 경우

• 사전순 앞서는 "AAAA"로 먼저 교체해주고 더이상 "AAAA"로 교체할 수 없을 땐 "BB"로 교체해준다.
• 해당 원소를 탐색해준 다음 마지막 원소의 경우를 제외하고 '.'를 출력해준다.

입력받은 문자열을 split("\\.")로 잘라주니 답이 틀렸다고 나옴 -> 문자열을 split 할때 -1를 추가해줘야 빈값도 배열에 담을 수 있다.

String test = "AA,BB,CC,,EE,FF,"; 
String[] testArray = test.split(",", -1);

for(int i = 0; i < testArray.length; i++){
   System.out.println(testArray[i]);
}

[출처 : https://darusamu.tistory.com/entry]

 

💻 코드

import java.util.*;

public class BOJ1343{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        
        String str = sc.next();
        String[] strArr = str.split("\\.",-1);
        
        String result = "";
        int count=0;
        
        for(int i=0; i<strArr.length; i++){
            count = strArr[i].length();
            if(count%2!=0){
                result = "-1";
                break;
            }else{
                while(count>0){
                    if(count>=4){
                        result+="AAAA";
                        count-=4;
                    }else if(count>=2){
                        result+="BB";
                        count-=2;
                    }
                }
            }
            if(i!=strArr.length-1) result+=".";
        }
        
        System.out.println(result);
    }
}

 

💡 다른 사람 코드

입력값을 AAAA와 BB로 변경해주는 문제이니 replace() 함수를 사용해 문자열을 교체해주고

교체를 해준 후에도 X가 남아있다면 -1, 남아있지 않다면 그대로 바꾼 문자를 출력해주면 된다.

import java.util.*;
 
public class BOJ1343 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        String A = "AAAA", B = "BB";
        
        s = s.replaceAll("XXXX", A);
        String ans = s.replaceAll("XX", B);
        
        if(ans.contains("X")) {
            ans = "-1";
        }
 
        System.out.println(ans);
    }
}