취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11541번 문제인 At most twice이다.
문제는 아래 링크를 확인하자.

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

주어진 수보다 작거나 같은 수중 각 자리에 등장하는 숫자들의 등장횟수가 2회 이하가 되는 가장 큰 수를 찾는 문제이다.

주어진 수가 조건을 만족할 때까지 most significant digit(가장 왼쪽 자리)부터 읽으면서 처음으로 등장횟수가 3회째 되는 숫자가 등장하면 (1) 해당 자리에 등장하게 되는 수가 2회 이하 등장한 수가 될 때까지 1씩 감소시키고 (2) 그 숫자가 '0'보다 작아졌다면 앞자리의 숫자들로 구성된 숫자열을 정수로 생각해 1을 뺀 다음 뒤의 모든 자릿수를 '9'로 변경, 그렇지 않다면 그리디하게 사용할 수 있는 가장 큰 숫자부터 차례대로 이용해 뒤의 문자열을 채우는 것을 반복하자. 단, 이 과정에서 주어진 수가 leading zero를 가지면 안되므로 각 단계에서 leading zero를 가지는 수가 나타날 경우 그 zero를 제거해주자.

과정 (2)의 첫 번째 경우에서 단순히 뒤의 모든 자릿수를 '9'로 변경한 이유는 1을 뺀 앞의 자릿수들이 조건(모든 숫자들은 2회 이하 등장)을 만족하는지 다시 확인할 필요가 있기 때문에 두 번째 경우의 과정을 단순히 생략하고 가능한 가장 큰 수를 나타내게끔 각 자리를 조정한 것으로 큰 의미가 있지는 않다.

이 과정은 수가 점점 작아지므로 항상 종료되는 것이 보장되며, 특히 그 반복 횟수가 충분히 적음(1을 빼고 앞의 자릿수를 다시 점검하는 횟수는 자릿수에 비례한 횟수만큼만 일어날 수 있음)을 어렵지 않게 관찰할 수 있다. 따라서 위의 알고리즘은 문제를 해결하기에 충분히 빠름을 알 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <cstring>
using namespace std;

int cnt[128];
int slen;
string s;

bool chk3() {
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i < slen; i++) {
		cnt[s[i]]++;
		if (cnt[s[i]] == 3) return 1;
	}
	return 0;
}

void func() {
	if (s.front() == '0') {
		s = s.substr(1, slen - 1);
		slen--;
		return;
	}
	memset(cnt, 0, sizeof(cnt));
	for (int i = 0; i < slen; i++) {
		cnt[s[i]]++;
		if (cnt[s[i]] < 3) continue;
		
		while (cnt[s[i]] == 3) {
			cnt[s[i]]--;
			s[i]--;
			cnt[s[i]]++;
		}
		if (s[i] < '0') {
			s[i] = '9';
			for (int j = i - 1; j > -1; j--) {
				s[j]--;
				if (s[j] < '0') s[j] = '9';
				else break;
			}
			for (int j = i + 1; j < slen; j++) s[j] = '9';
		}
		else {
			char idx = '9';
			for (int j = i + 1; j < slen; j++) {
				while (cnt[idx] > 1) idx--;
				s[j] = idx;
				cnt[idx]++;
			}
		}
		break;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s; slen = s.length();
	if (s.length() > 18) s = "999999999999999999", slen = 18;
	while (chk3() || s.front() == '0') func();
	cout << s;
}