[백준] 20310 타노스

풀이

사전순으로 가장 빠른 것을 구하는 것이기 때문에, 0은 제일 뒤에서부터 빼고, 1은 제일 앞에서부터 빼면 된다.

# 타노스
# 0과 1로 이루어진 문자열 S
# S가 포함하는 0의 개수와 S가 포함하는 1의 개수는 모두 짝수

# S를 구성하는 문자 중 절반의 0과 절반의 1을 제거해 새로운 문자열 S' 를 만들고자 한다.
# S'로 가능한 문자열 중 사전순으로 가장 빠른 것을 구해라

# 사전 순으로는 0이 1보다 앞에 있음
# 즉 0은 가장 뒤에서부터 빼고, 1은 가장 앞에서 부터 빼고

import sys
input = sys.stdin.readline
s = input()
half_zero = s.count('0') / 2 
half_one = s.count('1') / 2
# 0을 뺄 인덱스 저장
zero_arr = []
# 1을 뺄 인덱스 저장
one_arr = []

# 0빼기, 뒤에서부터
zero_cnt = 0
for i in range(len(s)-1,-1,-1):
    if s[i] == '0':
        zero_arr.append(i)
        zero_cnt+=1
    # half_len 이면 종료
    if zero_cnt == half_zero:
        break
# 1빼기, 앞에서부터
one_cnt = 0
for i in range(0,len(s)):
    if s[i] == '1':
        one_arr.append(i)
        one_cnt+=1
    # half_len 이면 종료
    if one_cnt == half_one:
        break
# 기록한 인덱스 빼고 나머지 다 포함
ans = []
for i in range(0, len(s)):
    if i in zero_arr or i in one_arr:
        continue
    ans.append(s[i])
# 정답 출력
print(''.join(ans))