[JAVA] BOJ(백준) - 민겸 수 - 21314

문제내용

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

21314번: 민겸 수

민겸이는 로마 숫자를 보고 굉장히 흥미롭다고 생각했다. 그래서 민겸이는 새로운 수 체계인 민겸 수를 창조했다.

민겸 숫자는 0 이상의 정수 N에 대해 10N 또는 5 × 10N 꼴의 십진수를 대문자 M과 K로 이루어진 문자열로 표기한다. 10N 꼴의 십진수는 N + 1개의 M으로, 5 × 10N 꼴의 십진수는 N개의 M 뒤에 1개의 K를 이어붙인 문자열로 나타낸다. 즉, 아래 표처럼 나타낼 수 있다.

변환 전	변환 후
1	M
5	K
10	MM
50	MK
100	MMM
500	MMK
1000	MMMM
5000	MMMK
...	...

민겸 수는 한 개 이상의 민겸 숫자를 이어붙여 만든다. 예를 들어, 민겸 수 MKKMMK는 MK, K, MMK의 세 민겸 숫자를 이어붙여 만들 수 있다.

민겸 수를 십진수로 변환할 때는, 1개 이상의 민겸 숫자로 문자열을 분리한 뒤, 각각의 민겸 숫자를 십진수로 변환해서 순서대로 이어붙이면 된다. 민겸 숫자를 십진수로 변환하는 것은 십진수를 민겸 숫자로 변환하는 과정을 거꾸로 하면 된다. 예를 들어, 민겸 수 MKKMMK는 아래 그림과 같이 여러 가지 십진수로 변환할 수 있다.

민겸이는 위와 같이 하나의 민겸 수가 다양한 십진수로 변환될 수 있다는 사실을 알았다. 문득 민겸이는 변환될 수 있는 십진수 중 가장 큰 값과 가장 작은 값이 궁금해졌다. 민겸이를 위해 하나의 민겸 수가 십진수로 변환되었을 때 가질 수 있는 최댓값과 최솟값을 구해주자.

입력

민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다.

출력

주어진 민겸 수가 십진수로 변환되었을 때 가질 수 있는 값 중 가장 큰 값과 가장 작은 값을 두 줄로 나누어 출력한다.

---

문제풀이

최댓값 최솟값을 찾는 문제로 단순하게 생각하면 최댓값이 되기 위해선 앞자리가 클수록, 최솟값은 앞자리가 작을수록 최솟값이 된다. 이를 기본 생각으로 문제에 접근하게 되면 아래와 같은 생각을 할 수 있다.

 

M만 있을때는 앞자리가 1, M에 K가 붙었을땐 앞자리가 5가된다.

즉, M이 나왔을때 K가 붙냐 안붙냐에 따라서 최대 최소값을 나눌수 있게된다.

 

최대값

M이 나왔을때 K가 나올때까지 탐색하고 M...K = 500...의 값을 넣어준다.

M 없이 K만 혼자 나온다면 바로 5로 바꿔준다.

 

최솟값

M이 나왔을대 K가 나올때까지 탐색하고 M.... = 100... 의 값을 넣어준다.

K가 나올때마다 5로 바꿔준다.

 

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String mg = br.readLine();
		
		StringBuilder sb = new StringBuilder();
		int cnt=0;
		boolean flag =false;
		
		String big = bigNum(sb, flag, cnt, mg);//최대값
		String small = smallNum(sb, flag, cnt, mg);//최소값
		
		System.out.println(big);
		System.out.println(small);
	}
	
	public static String bigNum(StringBuilder sb, boolean flag, int cnt, String str) {
		for(int i=0; i<str.length(); i++) {
			char ch = str.charAt(i);
			if(!flag && ch=='K') sb.append(5);//M없이 K가 나왔을때
			if(ch=='M') {//M개수 카운트
				cnt++;
				flag = true;
			}
			else if(flag && ch=='K') {//M이 있는 상태에서 K가 나왔을때
				sb.append(5).append("0".repeat(cnt));
				flag = false;
				cnt = 0;
			}
		}
		//cnt가 남아있다 -> 남은 M이 있다.
		if(cnt!=0 ) sb.append("1".repeat(cnt));
		return sb.toString();
	}
	
	//최댓값 로직과 같음.
	public static String smallNum(StringBuilder sb, boolean flag, int cnt, String str) {
		sb.setLength(0);
		flag = false;
		cnt = 0;
		for(int i=0; i<str.length(); i++) {
			char ch = str.charAt(i);
			if(!flag && ch=='K') sb.append(5);
			if(ch=='M') {
				cnt++;
				flag = true;
			}
			else if(flag && ch=='K') {
				sb.append(1).append("0".repeat(cnt-1)).append(5);
				flag = false;
				cnt = 0;
			}
		}
		if(cnt!=0) sb.append(1).append("0".repeat(cnt-1));
		return sb.toString();
	}
}

---

마치며

예전에 프로그래머스인지,, 리트코드인지 기억은 잘안나는데 로마숫자를 이용한 문제가 있었다.

유사한 문제였다고 기억하는데 암튼 이 문제는 최대값, 최소값이 되는 조건만 안다면 쉽게 구현 가능할꺼라고 생각한다.

그리디스럽다.