백준 20310 - 타노스

문제 설명

어느 날, 타노스는 0과 1로 이루어진 문자열 S$S$를 보았다. 신기하게도, S$S$가 포함하는 0의 개수와 S$S$가 포함하는 1의 개수는 모두 짝수라고 한다.

갑자기 심술이 난 타노스는 S$S$를 구성하는 문자 중 절반의 0과 절반의 1을 제거하여 새로운 문자열 S′$S'$를 만들고자 한다. S′$S'$로 가능한 문자열 중 사전순으로 가장 빠른 것을 구하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 1과 0으로 이루어진 문자열이 주어지면 1과 0을 정확히 절반으로 줄여 만들 수 있는 문자열 중 사전순으로 가장 빠른 문자열을 만드는 것이다.

1과 0이 모두 짝수로 주어지기 때문에 예외는 생각할 필요가 없다.

 

사전순으로 가장 빠른 문자열을 만드는 것은 간단하다.

0이 앞에 많이 나오며 1이 뒤에 나오면 된다.

즉, 앞에서부터 0은 포함하며 1은 버리면 된다.

이때, 0은 0의 개수의 절반만을 포함해야 하며 1역시 마찬가지이다.

정리하자면, 앞에서부터 0의 절반은 포함하고 1의 절반은 버리면서 진행한다.

 

따라서, 입력의 0과 1의 개수가 필요하다.

이를 bitset을 이용하여 1의 개수를 세어주었다.

const int size = N.length();
bitset<500> checkCnt(N);

int oneCntHalf = checkCnt.count() / 2;
int zeroCntHalf = (size - checkCnt.count()) / 2;

 

이후, 앞서 말한 과정을 진행하면 된다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>

using namespace std;

string N;

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

    cin >> N;

    const int size = N.length();
    bitset<500> checkCnt(N);

    int oneCntHalf = checkCnt.count() / 2;
    int zeroCntHalf = (size - checkCnt.count()) / 2;

    string ans;
    int oneCnt = 0;
    int zeroCnt = 0;
    for (int i = 0; i < size; i++)
    {
        if (N[i] == '0')
        {
            if (zeroCnt >= zeroCntHalf) continue;

            zeroCnt++;
            ans += N[i];
        }
        else 
        {
            if (oneCnt < oneCntHalf)
            {
                oneCnt++;
                continue;
            }
            else
            {
                ans += N[i];
            }
        }
    }

    cout << ans;

    return 0;
}

---