[코드포스 Practice14] E. Balanced Ternary String

 

ㅠ____ㅠ 코드가 더럽다

근데 이 방법 밖에 생각 안 나서 어쩔 수 없었음 (게다가 맞긴 맞았다)

 

먼저 간단히 제외할 수 있는 경우를 제외했다.

처음부터 2 / 2 / 2 처럼 개수 맞게 들어온 경우는 바로 출력하고 종료

다음으로 아예 더러운 경우 (전부 0 / 000000) 이런건 0 - 1 - 2 순서대로 출력하고 종료

 

이제 남은 건 012 전부 개수가 안 맞거나 하나는 0이고 나머지 두 개만 맞는 경우만 남았다. 

 

그 중 하나 0이고 나머지 두 개만 조정하는 것부터 코드짰다.

0이랑 2인데 2가 더 필요하면 뒤에서부터 0을 2로 고치고.. 0이 더 필요하면 앞에서부터 2를 0으로 고치고..

 

이런 식으로 로직짰음... 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
 
using namespace std;
using i64 = long long;

void make_two_zero(int a, int b, int n1, int n2, vector<int> &arr)
{
    if (n1 > 0)
    {
        int num = n1;
        for (int i = arr.size() - 1; i >= 0; i--)
        {
            if (arr[i] == a)
            {
                arr[i] = b;
                num--;
            }
            if (num == 0)
                break ;
        }
    }
    else
    {
        int num = n2;
        for (int i = 0; i < arr.size(); i++)
        {
            if (arr[i] == b)
            {
                arr[i] = a;
                num--;
            }
            if (num == 0)
                break ;
        }
    }
}

void print_same(int n)
{
    for(int i = 0; i < 3; i++)
    {
        for (int j = 0; j < n; j++)
        {
            printf("%d", i);
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    vector <int> arr(n);
    vector <int> count(3, 0);
    for (int i = 0; i < n; i++)
    {
        scanf("%1d", &arr[i]);
        count[arr[i]]++;
    }
    //변경할 필요가 없는 경우
    if (count[0] == count[1] &&
        count[2] == count[1] &&
        count[0] == count[2])
    {
        for (int i = 0; i < n; i++)
            printf("%d", arr[i]);
        return 0;   
    }
    //전부 다 바꿔야 하는 경우
    if (count[0] == n ||
        count[1] == n ||
        count[2] == n) 
    {
        print_same(n/3);
        return 0;   
    }
    //바꿔야 하는 횟수 계산
    for(int i = 0; i < 3; i++)
    {
        count[i] -= n/3;
    }
    //0인게 하나도 없을 때
    if (count[0] != 0 &&
        count[1] != 0 &&
        count[2] != 0)
    {
        
        if ((count[0] > 0 && count[2] < 0) || (count[0] < 0 && count[2] > 0))
        {
            if (abs(count[0]) < abs(count[2]))
            {
                make_two_zero(0, 2, count[0], -1 * count[0], arr);
                count[2] += count[0];
                count[0] = 0;
            }
            else
            {
                make_two_zero(0, 2, count[2] * -1, count[2], arr);
                count[0] += count[2];
                count[2] = 0;
            }
        }
        else
        {
            if (abs(count[0]) < abs(count[1]))
            {
                make_two_zero(0, 1, count[0], -1 * count[0], arr);
                count[1] += count[0];
                count[0] = 0;
            }
            else
            {
                make_two_zero(0, 1, count[1] * -1, count[1], arr);
                count[0] += count[1];
                count[1] = 0;
            }
        }
    }
    if (count[0] == 0)
    {
        make_two_zero(1, 2, count[1], count[2], arr);
    }
    else if (count[1] == 0)
    {
        make_two_zero(0, 2, count[0], count[2], arr);
    }
    else
    {
        make_two_zero(0, 1, count[0], count[1], arr);
    }
    
    for (int i = 0; i < n; i++)
        printf("%d", arr[i]); 

    
    return 0;
}

 

문제는 전부 다 고쳐야 하는 경우...

별 생각없이 먼저 0, 1만 바꾸고 다음으로 1, 2를 바꾸면 되겠지 싶었는데

+3 +6 -9 이런거면 0, 1을 고치는 거 자체가 횟수를 불필요하게 늘리는 게 돼버린다. 

 

그래서 울며 겨자먹기로 저 숫자 세 개 중 양수 - 음수 조합인 걸 찾은 다음 그 숫자 두개를 바꿨다. 

위처럼 +3 +6 -9인 경우는 +3이랑 -9를 바꾸는 걸로...

 

경우를 전부 나눠가면서 짠거라 정말 복잡하고 계속 중간에 예외 있고... 힘들었음

암튼 그리디를 배웠으니깐 내일은 그리디로 코딩해봐야겠다. 헝

 

 

---

 

 

 

 

 

 

헝 코드 이해는 다 했는데

아무것도 없는 상태에서 저걸 짜라하면 짤 수 있을지 모르겠다.

 

약간 0부터 i까지 처리를 하는데 자기 이전 값은 다 맞다고 가정하고 값을 처리하는 그런.. 그런 느낌... 

어렵다

 

이제 D번 풀러 가야지