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

문제

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

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

입력

문자열 $S$가 주어진다.

출력

 $S'$로 가능한 문자열 중 사전순으로 가장 빠른 것을 출력한다.

제한

 $S$의 길이는 $2$ 이상 $500$ 이하이다.
$S$는 짝수 개의 0과 짝수 개의 1로 이루어져 있다.

• 서브태스크 1 (25점)
  $S$의 길이는 4의 배수이다.
  $S$의 홀수 번째 문자는 1, 짝수 번째 문자는 0이다.
• 서브태스크 2 (75점)
  추가적인 제약 조건이 없다.

예제 입출력

• 예제 입력 1

1010

• 예제 출력 1

01

• 예제 입력 2

000011

• 예제 출력 2

001

이 예제는 서브태스크 1의 조건을 만족하지 않는다.

Solution

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

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string inputString;
    cin >> inputString;
    int countZero = 0, countOne = 0;
    for(auto i : inputString){
        if(i == '0') countZero++;
        else countOne++;
    }
    int dstZero = countZero / 2;
    int dstOne = countOne / 2;
    while(countZero != dstZero){
        int idx = inputString.rfind('0');
        if(idx != string::npos){
            inputString.erase(idx,1);
            countZero--;
        }
    }
    while(countOne != dstOne){
        int idx = inputString.find('1');
        if(idx != string::npos){
            inputString.erase(idx,1);
            countOne--;
        }
    }
    cout << inputString << '\n';
}

간단하다. 말 그대로 데이터 내에 0과 1의 갯수를 반으로 줄이 되, 사전 순으로 배치되도록 해야한다.
즉 0은 뒤에서부터, 1은 앞에서부터 날려먹어야 한다는 의미다.

최대한 간단하게 짜기 위해서 String 라이브러리를 적극 활용했다.

string inputString;
cin >> inputString;
int countZero = 0, countOne = 0;
for(auto i : inputString){
    if(i == '0') countZero++;
    else countOne++;
}
int dstZero = countZero / 2;
int dstOne = countOne / 2;

0과 1의 갯수를 센다. 그리고 각 갯수의 반절을 저장해둔다.

while(countZero != dstZero){
    int idx = inputString.rfind('0');
    if(idx != string::npos){
        inputString.erase(idx,1);
        countZero--;
    }
}
while(countOne != dstOne){
    int idx = inputString.find('1');
    if(idx != string::npos){
        inputString.erase(idx,1);
        countOne--;
    }
}
cout << inputString << '\n';

find, rfind 이 두가지 라이브러리 함수를 써먹어보았다. 사실 각 경우마다 for문 돌리는것도 방법이긴 하다. 그렇지만 가능하면 C++인데 C++ 답게 쓰는 게 좋지 않을까 하는 생각에 이러한 함수들을 활용 해 보았다.
(사실 구현하기 너무 귀찮았다고 하자.)
find는 왼쪽부터 오른쪽, 우리가 흔히 생각하는 탐색 방향이라면 rfind는 역방향 탐색이다. 또한 erase에서 idx뒤에 들어가는 1 인수는 삭제하고자 하는 문자열의 길이라고 생각하면 된다. 한 글자만 삭제할 것 같으면 1을 입력해주면 된다. 이 파라미터에 아무 값도 저장되지 않는다면 idx 기준으로 나머지 문자열을 모두 삭제해버리니 조심할것.

string::npos 같은 경우엔 찾고자 하는 값이 없는 경우에 find,rfind의 결과값이 된다. 0이나 1을 찾을 때 마다 값을 삭제해버리고 countZero, countOne 각각 변수들을 1씩 깎아준다. for문으로 돌려도 될 법한 문제지만 erase 함수를 사용하기 때문에 인덱스별로 탐색하기가 어려울 것이라 판단했다. 복잡하게 코딩하기 싫기도 했지만.

string 관련 된 라이브러리 함수들을 잘 알아두는 것이 중요하다. 문자열 처리 프로그램 같은 경우는 파이썬이 확실히 유리하기는 하지만 C++로 코딩테스트를 준비하는 입장에서는 그런 문제만 파이썬으로 해결하기엔 헷깔릴 수도 있으니까.