[백준] 21314번: 민겸 수 (JavaScript, NodeJS)

문제

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

민겸 숫자는 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을 넘지 않는다.

출력

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

예제 입력 1 복사

MKM

예제 출력 1 복사

501
151

예제 입력 2 복사

MKKMMK

예제 출력 2 복사

505500
155105

정답 풀이

const path = process.platform === "linux" ? "/dev/stdin" : "input.txt"; // 리눅스로 테스트할 땐 따로 설정해주어야 합니다.
const input = require("fs").readFileSync(path).toString().trim().split("\n");

const string = input[0];

// 문제 풀이:
function solution(string) {
	const splited = string.split('');
	const maximum = findMaximum(splited);
	const minimum = findMinimum(splited);
	console.log(maximum);
	console.log(minimum);
}

function findMaximum(string) {
	let stack = [];
	let number = '';

	for (let i = 0; i < string.length; i += 1) {
		const item = string[i];

		if (item === 'M') {
			stack.push(item);
			continue;
		}

		if (item === 'K') {
			// const pushItme = stack.length ? String(5 * (10 ** stack.length)) : 5;
			if (stack.length) {
				number += '5';
				for (let i = 0; i < stack.length; i += 1) {
					number += '0';
				}
			} else {
				number += '5';
			}
			stack = [];
		}
	}

	if (stack.length) stack.forEach(_ => number += '1');
	return number;
}

function findMinimum(string) {
	let stack = [];
	let number = '';

	for (let i = 0; i < string.length; i += 1) {
		const item = string[i];

		if (item === 'M') {
			stack.push(item);
			continue;
		}

		if (item === 'K') {
			if (!stack.length) {
				number += '5';
			} else {
				number += '1';
				for (let i = 0; i < stack.length - 1; i += 1) {
					number += '0';
				}
				// number += (String(10 ** (stack.length - 1)));
				number += '5';
				stack = [];
			}
		}
	}

	if (stack.length) {
		number += '1';
		for (let i = 0; i < stack.length - 1; i += 1) {
			number += '0';
		}
	}
	return number;
}

// 제출
solution(string);

⭐ 문제 핵심 아이디어 ⭐
1. 그리디
2. 최솟값, 최댓값 구하는 메소드 따로 구현
3. 총 네 가지의 시나리오가 있음.
    -  M을 만났을 때
    -  K를 만났는데 앞에 M이 없을 때
    -  K를 만났는데 앞에 M이 있을 때
    -  M만 나열 됐을 때
각각의 시나리오에서 최댓값과 최솟값을 구하는 아이디어를 구현하면 됨

 

맨 처음에 문제풀 때

const pushItme = stack.length ? 5 * (10 ** stack.length) : 5;

이렇게 stack의 길이에 따라서 넣을 아이템을 결정하는 로직인데,

이 로직에는 큰 문제점이 하나있다.

 

최대 길이가 3000인 것을 고려는 했는데,

만약 M만으로 이루어진 3000개라면

10 거듭제곱 3000이 되는데, 그럼 컴퓨터가 나타낼 수 있는 number의 범위를 너무 가뿐히 넘어버리기 때문에

출력이 이상하게 나온다.

 

for (let i = 0; i < stack.length; i += 1) {
	number += '0';
}

그래서 위의 방식대로 거듭제곱이 아닌 string 형식으로 이어붙여야한다.

 

이것만 고려하면 크게 어렵지 않은 문제.