[그리디 #6] BOJ 1343 - 폴리오미노

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

1343번: 폴리오미노

 

접근 방법

매우 간단한 그리디 문제이다. 저번에 풀었던 거스름돈 문제와 같은 풀이로 해결이 가능하다.

https://parvegoongame.tistory.com/115

[그리디 #5] BOJ 14916 - 거스름돈

 

조금 생각해야하는 점은 어떻게 String을 받아서 AAAA나 BB로 대체하는냐이다.

 

이는 간단하게 String을 돌면서 X의 갯수를 세어 저장하도록 설정하였다.

 

예) XXXX...XX....

-> 4 2

 

이렇게 X의 수를 저장하였다면 이를 AAAA나 BB로 대체하는 로직을 만들자.

 

AAAA로 대체하려면, 기존 X의 갯수에서 -4를 한 값이 4의 배수이거나 2의 배수여야 한다.

(예를들어 -4 한 값이 3이면 대체가 불가능하므로 -1을 출력해야함. )

 

마찬가지로 기존 X의 갯수에서 -2를 한 값이 2의 배수여야 한다.

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

string str;
vector<char> res;
vector<int> xCnt;

void addAAAA() {
	for(int i=0;i<4;i++)
		res.push_back('A');
}

void addBB() {
	for (int i = 0; i < 2; i++)
		res.push_back('B');
}

void addDot() {
	res.push_back('.');
}

void replace(int rest) {
	while (rest > 0) {
		if ((rest - 4 >= 0) && ((rest - 4) % 4 == 0 || (rest - 4) % 2 == 0)) {
			addAAAA();
			rest -= 4;

			//cout << "AAAA" << endl;
		}
		else if ((rest - 2 >= 0) && ((rest - 2) % 2 == 0)) {
			addBB();
			rest -= 2;

			//cout << "BB" << endl;
		}
		else {
			//cout << "rest : "<< rest << "<-EXIT" << endl;

			cout << -1;
			exit(0);
		}
	}
}

void solution() {
	int idx = 0;
	for (int i = 0; i < str.length(); i++) {
		if (str[i] == 'X') {
			replace(xCnt[idx]);
			i += (xCnt[idx++] - 1);
		}
		else {
			addDot();
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> str;
	bool flag = false;
	int cnt = 0;
	int idx = 0;
	while (idx <= str.length()) {
		if (idx == str.length() && flag) {
			xCnt.push_back(cnt);
			break;
		}

		if (str[idx] == 'X') {
			cnt++;
			flag = true;
		}
		else {
			if (flag) {
				xCnt.push_back(cnt);
				cnt = 0;
				flag = false;
			}
		}
		idx++;
	}

	solution();

	for (int i = 0; i < res.size(); i++)
		cout << res[i];
}