백준 17828번 : 문자열 화폐 [문자열/스택/C/C++]

문제 링크 : https://www.acmicpc.net/problem/17828

17828번: 문자열 화폐

문제 |

작년에 소수나라에 다녀온 하나는, 올해는 문자열나라로 관광을 가려고 한다. 문자열나라에서는 특이하게 알파벳 대문자로 구성된 문자열을 화폐로 사용한다.

문자열나라에서 'A'는 1의 가치, 'B'는 2의 가치, ..., 'Z'는 26의 가치를 가지고 있으며, 이 알파벳들을 붙여 화폐로 쓰일 문자열을 만든다. 예를 들어, "HONGIK"의 가치는 8 + 15 + 14 + 7 + 9 + 11 = 64가 된다.

소수나라에서 특이한 화폐 때문에 큰 스트레스를 받았던 하나는, 이번에는 정확한 소비 계획을 세워 미리 문자열 화폐로 돈을 환전해가려고 한다. 하나가 가져갈 문자열은 딱 하나이며, 길이는 N이고, 가치는 X여야 한다. 그리고 물론 알파벳 대문자로만 이루어져 있어야 한다.

그런데 환전소에서는 사전 순으로 앞서는 문자열을 우선적으로 환전해준다고 한다! 여행 준비에 정신이 없는 하나를 위해, 조건을 만족하면서 사전 순으로 가장 앞서는 문자열 구해주자.

 

입력 |

첫 번째 줄에 문자열의 길이 N(1 ≤ N ≤ 5,000,000)과, 문자열의 가치를 나타내는 정수 X(1 ≤ X ≤ 500,000,000)가 공백으로 구분되어 주어진다.

 

출력 |

첫째 줄에 그룹 단어의 개수를 출력한다.첫 번째 줄에 조건을 만족하는 문자열 중, 사전 순으로 가장 앞서는 것을 출력한다. 만약 그런 문자열이 하나도 존재하지 않으면, "!"(따옴표 없이)를 출력한다.

 

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;

int main(void)
{
	int count, num;
	stack<char> alphabet;
	cin >> count >> num;

	if (count * 26 < num || num < count)
	{
		cout << "!";
	}

	else {
		for (int i = 0; i < count; i++)
		{
			int temp = count - i - 1;
			if (num - temp > 26)
			{
				alphabet.push('Z');
				num = num - 26;
			}
			else
			{
				alphabet.push(num - temp + 64);
				num = num - (num - temp);
			}
		}
	}

	while (!alphabet.empty())
	{
		cout << alphabet.top();
		alphabet.pop();
	}

	return 0;
}

단계별로 분류에서 문자열로 분류되어 있는 문제는 아닌데, 일단 문자열 가지고 노는 문제라 분류를 문자열로 했다. 정작 문제는 스택 자료구조를 활용하여 풀었다. 스택 자료구조를 소스 내에 직접 구현하기 보다 라이브러리를 가져와서 풀었는데, 스택을 구현하는 소스는 따로 포스팅을 만들어서 올려보도록 하겠다.

 

코드 리뷰를 들어가보자. 문제에서 생각해야 할 점은 크게 2가지였다. 하나는 숫자를 어떻게 문자열로 바꿀 것인지 알고리즘을 만드는 것과, 다른 하나는 만들어진 문자열을 어떻게 저장시키고 출력할 것인가에 대한 문제였다. 문자열로 바꾸는 것부터 살펴보자. 첫 번째 예제 사례에서 문자열이 출력된 패턴을 보면 다행히 무작위로 알파벳을 집어넣은 것이 아니라 뒤로 갈수록 알파벳의 순서도 뒤로 치우쳐져 있다는 것을 알 수 있다. 즉, 뒤에 큰 수를 지니는 알파벳들을 먼저 채워넣고 남는 숫자에 적은 수를 지니는 알파벳을 채워넣는 것이다.

 

if (count * 26 < num || num < count)
{
	cout << "!";
}

알파벳으로 변환하기 전에 우선 예외처리를 해주어야 한다. 입력을 받을 때 처음 집어넣는 숫자(count)는 알파벳의 개수를 의미한다. 이 알파벳들을 모두 숫자로 변환시켜 더한 값이 뒤에 입력한 숫자(num)이다. 그런데 뒤에 입력하는 숫자(num)이 너무 커서 앞에 집어넣을 만한 공간(count)을 충분히 주지 않는다면 문제에서 주어졌듯이 "!"을 출력해 예외처리를 해주어야 한다. 그래서 입력받을 수 있는 알파벳이 지니는 최대 숫자가 26(Z)이므로 26 * 개수(count)를 해주면 해당 케이스에서 가장 크게 입력 받을 수 있는 숫자의 크기를 알 수 있고, 이것보다는 입력받는 숫자(num)가 작아야 한다.

(조건에서는 크면 "!" 출력하게끔 작성)

 

그리고 또 예외처리 해주어야 할 조건이 있다. 알파벳 개수(count)보다 입력하는 숫자(num)가 작을 경우이다. 만약 개수(count)가 6이고 입력하는 숫자(num)도 6이라면 출력 값은 "AAAAAA"가 나오게 된다. 그런데 여기서 입력하는 숫자(num)이 1이라도 작아지게 되면 마지막 칸을 채울 수가 없기 때문에 문제에서 언급한 문자열이 존재하지 않는 상황이 되므로 "!"을 출력한다.

for (int i = 0; i < count; i++)
{
	int temp = count - i - 1;
	if (num - temp > 26)
	{
		alphabet.push('Z');
		num = num - 26;
	}
	else
    	{
		alphabet.push(num - temp + 64);
       		num = num - (num - temp);
	}
}

이제 숫자를 알파벳으로 변환하는 핵심 코드를 살펴본다. 알파벳으로 변환할 때는 우선 뒤에 올 문자들을 최대한 가장 큰 숫자인 'Z'로 채워준다. 이 조건을 충족하기 위해서는 입력한 숫자(num)에서 채워야하는 나머지 문자 개수(temp)를 뺀 값이 'Z'에 상응하는 26을 넘어야 한다. num - temp값이 26을 넘는다면 무조건 'Z'를 스택(alphabet)에 집어넣는다.

 

처음부터 26이 넘지 않을 수도 있고 for문이 돌아가면서 num값이 26보다 작아지는 경우가 있다. 이 때, else문 안의 코드가 작동한다. 여기서 num에서 temp를 빼는 이유는 현재 채워야하는 문자가 출력되더라도 나머지 남은 개수(temp)를 채우지 못하면 "!"가 출력되기 때문에 이를 방지하기 위하여 적어도 1의 값에 해당하는 "A"를 나머지(temp)에 집어넣는다고 생각하고 최소값을 빼주는 것이다. 예를 들어, 채워야하는 개수(count)가 6이라고 치면 현재 채워야하는 방 1개를 빼고도 나머지 5개 방에 최소 1의 값에 해당하는 "A"를 모두 채워야 "!"가 출력되지 않으므로 이 예시에서 temp값은 5가 된다.

 

그리고 이 temp값을 뺀 나머지 값(num - temp)은 해당 순서에서 최대로 넣을 수 있는 문자가 되므로 곧바로 아스키 코드 변환을 통해 스택(alphabet)에 집어넣으면 된다. 그리고 if문과 else문 모두 조건 처리가 끝났으면 끝에 스택에 넣은 값만큼 num에서 값을 빼서 num값을 업데이트 시켜준다.

 

마지막으로 스택을 쓰는 이유에 대해서 이야기하면, 꼭 스택을 써야할 필요는 없다. 다른 분들 문제 푼 코드 찾아보니까 string 문자열을 이용해서 푸신 분들도 계셨다. 알고리즘이 겉으로 보기에 상이하긴 하지만 나는 문자열을 뒤에서부터 구성하기 때문에 역으로 출력하는 과정을 상상하기가 쉬워서 스택 자료구조를 사용했을 뿐이다.