BaekJoon 1474번: 밑 줄(C++)

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

1474번: 밑 줄

풀이법

1) 규칙을 찾으면 쉽게 풀 수 있는 그리디 알고리즘이었다.

2) 가장 중요한 부분은  'A' < 'B' < 'C' < ... < 'Z' < '_' < 'a' < 'b' < 'c' < ... < 'z' 이며, 사전 순으로 가장 앞서는 단어를 출력해야 한다는 것이다.

3) 입력 받은 값들을 토대로 m의 길이와 단어의 길이를 통해 최소 _가 들어갈 개수를 파악해 주었다. 이후 추가적으로 _를 넣을 수 있는 개수를 파악하므로서 문제를 해결하고자 하였다.

	int min_ = (m-wordLen) / (n - 1);
	int leftOver = (m-wordLen) - (min_ * (n - 1));

앞서 얻은 값을 바탕으로 다음 값의 첫 글자가 대문자 일때와 소문자 일때는 나누어 주었다.

• 대문자일 경우, 현재 추가로 넣어야할 문자의 개수와 기본적인 _의 개수 외에 m을 맞추기 위한 추가적인 _ 개수가 같다면 _를 추가로 한 개씩 넣어주었다.
• 반면 소문자일 경우, _이 앞에 들어갈 수록 사전순으로 빠른 것이니 _을 넣을 수 있는 것들이 있다면 최대한 앞쪽에서 넣을 수 있도록 코딩을 진행하였다

#include <string>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <unordered_map>
#include <math.h>
using namespace std;

int n, m;
vector<string> words;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	int wordLen = 0;
	for (int i = 0; i < n; i++)
	{
		string s; cin >> s;
		wordLen += s.size();
		words.push_back(s);
	}
	int min_ = (m-wordLen) / (n - 1);
	int leftOver = (m-wordLen) - (min_ * (n - 1));
	string s = words[0];
	int leftWord = words.size() - 1;
	for (int i = 1; i < words.size(); i++)
	{
		if (words[i][0] >= 'A' && words[i][0] <= 'Z')
		{
			if (leftWord == leftOver)
			{
				for (int j = 0; j < min_+1; j++)
				{
					s += '_';
				}
				s += words[i];
				leftOver--;
				leftWord--;
			}
			else
			{
				for (int j = 0; j < min_; j++)
				{
					s += '_';
				}
				s += words[i];
				leftWord--;
			}
		}
		else//소문자
		{
			if (leftOver > 0)
			{
				for (int j = 0; j < min_ + 1; j++)
				{
					s += '_';
				}
				s += words[i];
				leftOver--;
				leftWord--;
			}
			else
			{
				for (int j = 0; j < min_; j++)
				{
					s += '_';
				}
				s += words[i];
				leftWord--;
			}
		}
	}
	cout << s;
}