[백준 20310] 타노스

www.acmicpc.net/problem/20310

20310번: 타노스

문자열 알고리즘 문제

문자열 내의 순서는 고정이라는 전제하에 풀어야 한다. 아니면 25점 ㅠ

 

0과 1 절반씩을 날린다고 했으므로 사전순으로 빠른 것을 구하기위해 0은 뒤에 절반을, 1은 앞에 절반을 날린다.ㅏ

덱을 사용해도 되지만 배열에서 해결하기 위해 머지소트에서 사용하는 로직을 사용했다.

 

#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
char s[501];
int main(void)
{
  scanf("%s", s);
  int n = strlen(s);
  vector<int> zero;
  vector<int> one;
  for (int i = 0; i < n; i++)
  {
    if (s[i] == '0')
    {
      zero.push_back(i);
    }
    else
    {
      one.push_back(i);
    }
  }

  int sz = zero.size() / 2;
  int so = one.size() / 2;

  int left = 0, right = so;
  while (left < sz && right < so * 2)
  {
    if (zero[left] < one[right])
    {
      left++;
      printf("0");
    }
    else
    {
      right++;
      printf("1");
    }
  }

  while (left < sz)
  {
    printf("0");
    left++;
  }

  while (right < so * 2)
  {
    printf("1");
    right++;
  }

  return 0;
}