[Codeforces]1102D-Balanced Ternary String

[Codeforces]1102D-Balanced Ternary String

구현력이 얼마나 중요한지 일깨워 주는 문제. 

길이가 3의 배수이고 오직 0,1,2로만 이루어진 문자열이 주어진다. 이 문자열에서 등장하는 0,1,2의 빈도는 3개 모두 같도록 만들기 위해서 각 문자를 replace할 수 있는데, 이 때 replace 횟수가 최소가 되도록 하면서 동시에 사전순으로 가장 앞에 있는 문자열을 구하는 문제이다. 문제 난이도는 D번 치고 그렇게 어렵지는 않고, 실제로 이 문제를 접했을 때 솔루션도 금방 나왔다. 0,1,2의 등장 횟수가 n/3이 되도록 맞춰주기 위해서 많이 등장한 숫자는 적게 등장한 숫자에게 자신의 자리를 양보해주는 식이다. 그러면서 사전순 정렬도 고려해야 하기 때문에, 0이 제일 먼저 나와야하고 그 다음 1은 0을 먼저 등장시키고, 2는 0과 1을 먼저 등장시켜야 한다는 자잘한 우선순위 문제도 있다. 그렇게 어렵지는 않다. 하지만 이 문제의 진가는 구현을 어떻게 하느냐다. 무식하게 if문 여러개(6개 혹은 9개)를 때려 박으면 되기는 하나, 나는 별로 그렇게 풀고 싶지는 않았기 때문에 최대한 간결하게 짜려고 고민해보았다. 그래서 다른 사람들 코드를 계속 살펴보다가 우연히 잘 짠 코드를 발견해서 감명받고 이렇게 글을 남긴다.

#include<stdio.h>
#define SIZE 300009
char str[SIZE];
int cnt[3]={0};
int main(){
    int n;    scanf("%d %s",&n,str);
 
    for(int i=0 ; str[i] ; i++){
        int cur=str[i]-'0';
        cnt[cur]++;
    }
 
    int div3=n/3;
 
    for(int i=0 ; str[i] ; i++){
        int cur=str[i]-'0';
        if(cnt[cur]>div3){
            for(int j=0 ; j<cur ; j++){
                if(cnt[j]<div3){
                    cnt[j]++;
                    cnt[cur]--;
                    str[i]=j+'0';
                    break;
                }
            }
        }
    }
 
    for(int i=n-1 ; i>=0 ; i--){
        int cur=str[i]-'0';
        if(cnt[cur]>div3){
            for(int j=3-1 ; j>cur ; j--){
                if(cnt[j]<div3){
                    cnt[j]++;
                    cnt[cur]--;
                    str[i]=j+'0';
                    break;
                }
            }
        }
    }
 
    printf("%s",str);
    return 0;
}

for문 두개로 구성되어 있는데 첫번째 for문은 앞에서부터 뒤로 가면서 div3번보다 많이 등장한 숫자에 도달했을 때, 그 숫자보다 작으면서 div3번보다 적게 등장한 숫자로 대체하는 수행을 한다. 이렇게 했을 경우에는 000000을 처리하지 못하므로, 두번째 for문이 존재한다. 두번째 for는 뒤에서부터 앞으로 가면서 div3번보다 많이 등장한 숫자에 도달했을 때, 그 숫자보다 크면서 div3번보다 적게 등장한 숫자로 대체한다.