[BOJ 21314] 민겸 수

21314번: 민겸 수

- Greedy 문제 

  - 최댓값을 보장하게 배치하는 방법과 최솟값을 보장하게 배치하는 방법 고민

 

- 최댓값

K를 만난 경우 무조건 5를 붙이고 시작하고, M을 만난 경우는 K를 만나기 전까지는 누적해둔다.

MMM의 경우 100이 아닌 111이 나오도록 해야한다.

 

- 최솟값

K를 만난 경우 직전에 M으로 표현된 것들이 있었다면 모두 M을 1을 붙인 형태로 변형하고, 마지막에 K를 붙인다

MMM의 경우 최댓값과 달리 111이 아닌 100이 나오도록 해야한다.

 

[주석 설명 참고]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Queue;

public class Main {

	/*
	 * 1) 최댓값 : K를 만날 때까지 쭉 이어붙인다.
	 *    - 하나의 K도 못만나는 경우 정답은 String의 길이를 가진 1, 즉 111111 등이 된다.
	 *    - 하나의 K라도 만나는 경우 직전 + k까지바로 변환, 다음 단계도 동일하게 시작
	 *    
	 * 2) 최솟값 : K를 만날 때까지 쭉 이어붙인다.
	 *    - 하나의 K라도 못만나는 경우 정답은 String의 길이를 가진 M^N, 즉 100000 등이 된다.
	 *    - 하나의 k라도 만나는 경우 직전까지 변환 후 k도 바로 변환 후 다음 단계도 동일하게 시작
	 */
	
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String input = br.readLine();
		
		int len = input.length();
		
		FindMax(input, len);
		FindMin(input, len);
		
		wr.write(sb.toString());
		wr.close();
		br.close();
	}

	private static void FindMax(String str, int len) {
		
		int cnt = 0;
		for (int i=0; i<len; i++) {
			if (str.charAt(i) == 'K') { //5가 등장했다면
				sb.append(5); // 최댓값이기 때문에 5 붙이고 시작
				
				for (int j=0; j < cnt; j++) {
					sb.append(0); // 0 붙이기
				}
				cnt = 0;
			}
			else {
				cnt++;
			}
		}
		
		if (cnt != 0) { // 아직 추가되지 않은 수가 있다면 다 1인데
			for (int i=0; i<cnt; i++) {
				sb.append(1); // 최댓값이기 때문에 1씩 붙이는 걸로 시작한다.
			}
		}
		sb.append("\n");
		return;
	}

	private static void FindMin(String str, int len) {

		int cnt = 0;
		for (int i=0; i<len; i++) {
			if (str.charAt(i) == 'K') { // K를 만나는 순간이 온다면
				
				if (cnt > 0) { // 여태까지 1이 있었다면
					cnt--;
					sb.append(1); // 1 한개 추가하고
					
					for (int j=0; j<cnt; j++) // 최솟값이기 때문에 남아있는 cnt만큼 0 붙이기
						sb.append(0);
					
					cnt=0;
				}
				sb.append(5); // 마지막에 5 붙이기
			}
			else {
				cnt++;
			}
		}
		if (cnt != 0) { // 남아있는 수가 있다면
			cnt--;
			sb.append(1); // 1 한개 추가하고
			for (int j=0; j<cnt; j++) // 최솟값이기 때문에 남아있는 cnt만큼 0 붙이기
				sb.append(0);
		}
		return;
	}

}