백준 1474번 밑 줄 (C++)

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

1474번: 밑 줄

 

 실랜디 중 문제 이해가 안되서 애먹었던 문제다.  대문자 A.. Z < _ < a...z 소문자 이고 사전순으로 가장 앞에 오는 단어로 만들어보자 이게 대체 무슨말인데,,,

어려운 문제는 아닌데 설명이 개같아서 푼 사람이 적은것 같다. 해석하면 순서상으로 가장 앞에 오기 위해서는 대문자 보단 소문자앞에 _가 붙어있어야 사전상 앞으로 오게 되는 것이다. A B C _ a b c 순서이니 A b c 라 하면 A_b_c 이후 만약 _를 더 추가해야한다면 A__b_c 가 되어야하는 것이다. 왜? A이후 나오는 것은 _ 이기 때문이다. 

 

즉 

 

먼저 각 단어 사이에 같은 개수만큼 "_" 을 추가해놓은 후 루프를 돌면서 만약 소문자이면 _를 추가하여 1~N까지 루프를 돌고 아직 단어의 길이가 모자르다면 N~1 까지 역순으로 가며 대문자이면 _를 추가해주는 식으로 풀이했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int N, M;
vector<string> words;

int main() {
	ios_base::sync_with_stdio(NULL);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	string word;
	int wordlen = 0;
	for (int i = 0; i < N; i++) {
		cin >> word;
		words.push_back(word);
		wordlen += word.size();
	}
	//cout << wordlen;
	string tmp = "";
	for (int i = 0; i < (M - wordlen) / (N - 1); i++) {
		tmp += "_";
	}
	for (int j = 0; j < words.size() - 1; j++) {
		words[j] += tmp;
	}

	if ((M - wordlen) % (N - 1) != 0) { // 나누어 떨어지지 않음
		int cnt = M - wordlen - tmp.size() * (N - 1);
		int idx = 1;
		bool check = true;
		while (true) {
			if (check) {
				if (words[idx][0] <= 'z' && words[idx][0] >= 'a') { // 소문자라면
					words[idx - 1] += "_";
					cnt--;
				}
				idx++;
			}
			else {
				if (words[idx][0] <= 'Z' && words[idx][0] >= 'A') {
					words[idx - 1] += "_";
					cnt--;
				}
				idx--;

			}
			if (idx == N) {
				check = !check;
				idx--;
			}

			if (cnt == 0)
				break;
		}
	}


	string answer = "";
	
	for (auto a : words)
		answer += a;

	cout << answer << '\n';
	return 0;
}