[BOJ][C++] 백준 21314번: 민겸 수 (Silver I)

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

 

문제

민겸이는 로마 숫자를 보고 굉장히 흥미롭다고 생각했다. 그래서 민겸이는 새로운 수 체계인 민겸 수를 창조했다.
민겸 숫자는 0 이상의 정수N에 대해 10N또는 5 × 10N꼴의 십진수를 대문자M과K로 이루어진 문자열로 표기한다. 10N꼴의 십진수는N+ 1개의M으로, 5 × 10N꼴의 십진수는N개의M뒤에 1개의K를 이어붙인 문자열로 나타낸다. 즉, 아래 표처럼 나타낼 수 있다.
민겸 수는 한 개 이상의 민겸 숫자를 이어붙여 만든다. 예를 들어, 민겸 수MKKMMK는MK,K,MMK의 세 민겸 숫자를 이어붙여 만들 수 있다.
민겸 수를 십진수로 변환할 때는, 1개 이상의 민겸 숫자로 문자열을 분리한 뒤, 각각의 민겸 숫자를 십진수로 변환해서 순서대로 이어붙이면 된다. 민겸 숫자를 십진수로 변환하는 것은 십진수를 민겸 숫자로 변환하는 과정을 거꾸로 하면 된다. 예를 들어, 민겸 수MKKMMK는 아래 그림과 같이 여러 가지 십진수로 변환할 수 있다.

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

입력

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

출력

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

 

풀이

가장 중요한건 이 문제는 숫자로 다루면 안된다. 자릿수가 3000이 넘어간다

(unsigned long long int 어쩌구 이런거 다 안됨)

무조건 문자열로 다뤄야한다.

(애초에 내가 숫자와 수식으로 먼저 해봤는데 분기처리 때문에 코드만 더 복잡해지더라)

 

일단 K가 두개 이상 포함되는 민겸수가 없으므로 무조건 K를 기준으로 끊어야한다.

그리고 M은 M끼리 붙어있어야 한다.

 

최댓값을 만드려면 K가 나오는 순간

앞의 연속된 M뒤에 K를 붙인 민겸수를 구해서 문자열에 추가해주면 된다

K => 5, MK => 50, MMK => 500, MMMK => 5000

 

10^(앞에 M의 갯수)* 5 인데,

문자열로 치면 5 뒤에 앞M갯수만큼 0을 붙인 것과 같다

    string cur, big;
    for(char c : s) {
        if(c == m) {
            cur += "0";
        } else if(c == k) {
            big += "5" + cur;
            cur = "";
        }
    }

이런 느낌으로 구현 가능!

 

최솟값을 만드려면 K가 나오는 순간

앞의 연속된 M들을 민겸수로 구해서 문자열에 추가하고, 그 뒤에 K(=5)를 추가하면 된다.

K => 5, MK => 15, MMK => 105, MMMK => 1005

 

10*(앞 M 갯수) + 5 인데,

문자열로 치면 1 뒤에 앞M갯수-1 만큼 0을 붙이고 그 뒤에 5를 붙인 것과 같다.

    string cur, small;
    for(char c : s) {
        if(c == m) {
            cur += "0";
        } else if(c == k) {
            cur[0] = '1';
            small +=  cur + "5";
            cur = "";
        }
    }

 

 

이렇게 하면 K로 끝나는 민겸(수라고 쓰고 문자열이라고 읽는다) 문자열들은 처리가 된다.

놓치기 쉬운 부분은 M으로 끝나는 경우인데,

문자열을 반복문으로 다 돈 다음에 

cur에 남은 M관련 문자열들을 한번 더 처리해주면 된다

 

이때 최댓값을 구할땐

M => 1, MM => 11, MMM => 111, MMMM => 1111

최솟값을 구할 땐

M => 1, MM => 10, MMM => 100, MMMM => 1000

이렇게   바꿔서 추가해줘야한다.

 

정답 코드

// 풀이 : https://whkakrkr.tistory.com

#include <bits/stdc++.h>

using namespace std;

const char k = 'K';
const char m = 'M';

vector<string> solution(string s) {
    string big, small;
    
    string cur;
    for(char c : s) {
        if(c == m) {
            cur += "0";
        } else if(c == k) {
            big += "5" + cur;
            cur[0] = '1';
            small +=  cur + "5";
            cur = "";
        }
    }
    if(cur != "") { // 문자열이 M으로 끝났다면
        cur[0] = '1';
        small += cur;
        
        for(char c : cur) {
            big += '1';
        }
    }

    return {big, small};
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	string s;
	cin >> s;
	
	vector<string> ans = solution(s);
	
	cout << ans[0] << "\n" << ans[1];
	
    return 0;
}