[BOJ] 17958 Cycle String?

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

17958번: Cycle String?

일단 \(NO\)가 되는 조건을 알아보자.

1. 등장하는 문자가 1개인 경우 ex)\(aa...a\)

2. 등장하는 문자가 2개고, 한 문자가 \(2N-2\)개 이상인 경우 ex) \(aa...abb\)

나머진 모두 \(YES\)가 된다.

 

가장 많이 등장하는 문자를 \(X\)라 하자.

1. \(X\)를 \(min(N,cnt[X])\)개 놓는다.

2. \(X\) 가 아닌 다른 문자 한개를 놓는다.

3. \(X\)를 남은 개수만큼 놓는다.

4. \(X\)가 아닌 다른 문자를 쭉 내려놓는다.

놀랍게도, 이 문자열은 조건을 만족하는 문자열이 된다.

같은 문자열이 나올려면, \(X\)가 \(N\)개 연달아 오는 문자열 뿐인데, 그런 문자열은 최대 한번만 등장하므로, 이 문자열은 조건을 만족한다.

 

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long llINF = 1e18;
const int mod = 1e9+7;
const long long hashmod = 100003;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi;
typedef long long ll;
int n,cnt[27],mx,num;
char a[1000005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> a+1; n = strlen(a+1)/2;
	for(int i = 1;i <= 2*n;i++) {
		cnt[a[i]-'a']++;
	}
	for(int i = 0;i < 26;i++) {
		if(cnt[mx] < cnt[i]) mx = i;
		if(cnt[i]) num++;
	}
	if((n == 1&&cnt[mx] == 2*n)||(n != 1&&(cnt[mx] >= 2*n-1||(cnt[mx] == 2*n-2&&num == 2&&n != 2)))) {
		cout << "NO";
		return 0;
	}
	cout << "YES\n";
	for(int i = 0;cnt[mx]&&i < n;i++) {
		cout << (char)('a'+mx);
		cnt[mx]--;
	}
	for(int i = 0;i < 26;i++) {
		if(mx == i||!cnt[i]) continue;
		cout << (char)('a'+i);
		cnt[i]--;
		while(cnt[mx] > 0) cnt[mx]--, cout << (char)('a'+mx);
		while(cnt[i] > 0) cnt[i]--, cout << (char)('a'+i);
	}
}