[백준] -1343 (그리디, 구현)

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

1343번: 폴리오미노

 

[풀이 방안]

1. 사전순으로 가장 앞서는 답을 출력하라는 출력 조건이 있기 때문에 해당 조건을 만족하기 위해서는 그리디 알고리즘을 사용해서 풀면 된다.

  - 간단하게 AAAA를 사용할 수 있는 경우를 모두 빼고 나머지 BB를 출력할지 말지를 결정해주면 된다.

  - XXXXXXXXXX 라고 있다면 AAAAAAAABB를 출력해줘야 가장 사전순으로 앞서는 답이 된다.

  - XXXX 라면 BBBB가 아닌 AAAA를 출력해야 가장 앞서는 순서를 출력할 수 있게 된다.

  - 이를 위해서 모두 AAAA로 덮을 수 있는지를 확인하여 진행한다. (그리디)

2. AAAA로 덮을 수 있는 상황을 다 살펴봤다면 이제 남은 XX값이 있는지를 확인해서 BB를 덮을지 말지를 결정해주면 된다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();

	static String board;
	static int xCount;
	static int dotCount;

	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

	public static void main(String[] args) throws IOException {

		st = new StringTokenizer(br.readLine());

		board = st.nextToken();

		xCount = extractedCharCount('X');
		dotCount = extractedCharCount('.');

		// 1차적으로 2로 나누어지지 않는 x의 개수라면 애초에 덮을 수 없어서 -1 출력후 종료
		if (xCount % 2 != 0) {
			System.out.println(-1);
			return;
		} else if (dotCount == board.length()) {

			System.out.println(".".repeat(board.length()));
			return;

		}

		int pointerIndex = 0;
		int localXCounte = 0;

		while (pointerIndex < board.length()) {

			if (board.charAt(pointerIndex) != '.') {
				localXCounte += 1;

			} else if (board.charAt(pointerIndex) == '.') {

				if (localXCounte != 0) {
					int share = localXCounte / 4;
					int remainder = localXCounte % 4;

					if (remainder % 2 == 1) {
						System.out.println(-1);
						return;
					}
					sb.append("AAAA".repeat(share));
					if (remainder == 2) {
						sb.append("BB");
					}
				}

				sb.append(".");
				localXCounte = 0;
			}
			pointerIndex += 1;
		}

		if (localXCounte != 0) {
			int share = localXCounte / 4;
			int remainder = localXCounte % 4;

			sb.append("AAAA".repeat(share));
			if (remainder == 2) {
				sb.append("BB");
			}
		}

		System.out.println(sb.toString());

	}

	private static int extractedCharCount(char c) {
		int cnt = 0;
		for (int i = 0; i < board.length(); i++) {
			if (board.charAt(i) == c) {
				cnt += 1;
			}

		}
		return cnt;
	}

}

- 1차적으로 X의 개수가 홀수인 경우라면 덮을 수 없어서 -1로 return

- dot의 개수는 문자열 전체의 길이와 같다면 dot만 존재하기 때문에 그 개수만큼 dot 출력하고 return

- for문이 아닌 while문을 사용해서 X문자열의 개수를 세며 진행할 수 있게 한다.

- .닷이 아닌 문자라면 X이기 때문에 X개수를 늘려준다.

- 이때 닷을 만난다면 그전의 값이 dot이여서 x count 값이 0인지 아닌지를 확인해야 한다. 0인 경우라면 덮을 값이 필요 업이 닷 값만 그대로 표시해주면 되기 때문이다.

- 이때 닷 값을 만나고 그 전 값 역시 닷이 아닌 문자의 끝부분이라면 이때 해당 X문자열을 덮을 수 있는지 없는지 여부를 이곳에서 확인한다.

- 이 과정이 끝났다면 x를 count한 부분을 0으로 초기화해준다.

- 반복문의 마지막에는 pointerIndex를 1만큼 늘려 다음 작업을 진행한다.

- 반복문이 끝났음에도 불구하고 반복문을 돌면서 늘렸던 xcount가 남아있다면 이만큼 또 덮을 수 있는지를 확인해 덮어준다.