[백준] 1343번 폴리오미노(java,c++)

문제

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

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

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

입력

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

출력

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

 

이 문제는 이중 반복문을 사용해야 쉽게 풀수 있었다.

애초에 덮는다는 건 한번더 시도 하는건데...

오늘 푼 문제들을 해답을 보고 내 나름대로 정립 시킬려고 했는데.. 안된다..ㅜㅜ

 

이 문제를 풀때 단계를 생각하면서 문제에 접근하였다.

 

첫 번째는 AAAA와 BB만 존재할 경우를 생각했고,

두번째는 . 을 생각했다.

마지막은 나올 수 없는 방법을 생각했다.

 

package _2020_06_03.B;

import java.util.Scanner;

class Main {

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

		String board = sc.nextLine();
		String cover = "";

		int cnt = 0;
		for (int i = 0; i < board.length();) {

			if (board.charAt(i) == '.') {
				i++;
				cover += '.';
				continue;
			}

			for (int j = i; j < board.length() && board.charAt(j) == 'X'; j++) {
				cnt++;
			}

			i += cnt;

			if (cnt % 2 != 0) {
				System.out.println(-1);
				return;
			}

			while (true) {
				if (cnt >= 4) {
					cover += "AAAA";
					cnt -= 4;
				} else if (cnt == 2) {
					cover += "BB";
					cnt -= 2;
				} else {
					break;
				}

			}
		}

		System.out.println(cover);

	}
}

이건데..

j반복문이 하는 역할은  cover역할이다. 그러니까.. 이것으로 X의 값을 세는 뭐 그런거다.

하지만 .이 나온다면 세지 않는다...

그리고 끝나야 하니까 i값도 증가시켜준다.

 

 

그리고 나서 while문을 무한 반복문으로 만들었는데

그 이유는 1번이 아니라 여러번 반복해야되기 때문이다.

여기서 우리는 그리디 알고리즘이라는것을 알 수 있다.

2부터 하는 것이 맞을지도 모르지만.. 여기서는 4부터 해야한다. 왜냐하면 사전순이니까...

자 근데 왜 뺄까... 빼는 이유는 cnt로 덮을 무언가가 없다는 것을 뜻한다.

그러니까 덮을게 없으면 break문으로 나오겠지?

 

이걸 재귀로 만들려고 했는데 실패했다. 왜냐하면 애초에 리턴문이 두개 필요한데... 이걸 맵으로 저장할 수도 없고...ㅜㅜ

아무튼 실패했다. 그리디 할때는 그냥 하지 말아야지 ㅎㅎ

 

다 덮으면 또 반복한다. 근데 . 이면 그냥 덮은다. 그리고 1을 증가시킨다. 왜냐하면 .은 상관없기 때문이다. 

 

자 이제 다 되었으면 cover을 출력해주면된다.

 

이거 100ms나오는데 생각보다 빠르군...

 

 

c++ 코드 :

#include <bits/stdc++.h>
using namespace std;
string board;

int main(void) {
  cin >> board;

  string ans = "";
  int i = 0;
  int cnt = 0;
  while(i<board.length()) {

    if (board[i] == '.') {
      i++;
      ans += '.';
      continue;
    }

    for(int j  = i; j< board.length() && board[j] == 'X';j++) {
      cnt++;
    }
    
    if (cnt % 2 != 0) {
      cout << -1;
      return 0 ;
    }

    i+= cnt;


    while(true) {
    if (cnt >= 4) {
      ans += "AAAA";
      cnt-=4;
    } else if (cnt == 2) {
      ans += "BB";
      cnt-=2;
    } else {
      break;
      }
    }
  }

  cout << ans;
} 
 

어차피 자바소스랑 똑같으므로 생략! 다르게 생각하려고 했는데... 이건 뭐... 생각이 안나네 ㅜㅜ

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static boolean isEqualsStr(String str)
    {
        char temp = str.charAt(0);
        for(int i = 1; i < str.length(); i++)
        {
            if(temp !=str.charAt(i))
            {
                return false;
            }

        }
        return true;
    }

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

        List<String> ret=  new ArrayList<>();
        for (int i = 0; i < str.length(); )
        {
            if (str.charAt(i) == 'X')
            {
                if(i  + 4 <= str.length())
                {
                    String fourStr = str.substring(i, i+4);
                    if(isEqualsStr(fourStr))
                    {
                        i += 4;
                        ret.add("AAAA");
                        continue;
                    }
                }

                if(i + 2 <= str.length())
                {
                    String twoStr = str.substring(i,i+2);
                    if(isEqualsStr(twoStr))
                    {
                        i += 2;
                        ret.add("BB");
                        continue;
                    }
                    else
                    {
                        System.out.println(-1);
                        return;
                    }
                }
                else
                {
                    System.out.println(-1);
                    return;
                }
            }
            else
            {
                ret.add(".");
                i++;
            }
        }

        for(String s : ret)
        {
            System.out.print(s);
        }
    }
}