[BOJ] 20310 타노스

date

Jun 26, 2023

slug

boj-20310

author

status

Public

문제 링크

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

문제

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

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

문제풀이

처음 풀었을때는 문자열의 재배열이 가능한 줄알고

1의 갯수와 0의 갯수를 센 후, 0부터 반절, 1나머지 반절 출력했으나

25점 밖에 못맞음, 재배열이 불가.. 즉 삭제하여 붙이는 것 만가능

우선 갯수를 세서 0, 1의 갯수를 담당하는 배열에 넣고

0은 뒤에서부터 제거,

1은 앞에서부터 제거한 문자열을 새로만든다.

why?

0이 최대한 앞에 있고 1이 최대한 뒤에 있어야 가장 작은, 사전순으로 가장 먼저이면서 재배열을 하지 않는 조건을 만족하기 떄문이다.

파이썬 문제풀이 코드


S = list(str(input()))

zero_arr = []
one_arr = []

for i in S:
    if i == '0':
        zero_arr.append(0)
    elif i == '1':
        one_arr.append(1)

for i in range(len(zero_arr) // 2): # 반절
    for j in range(len(S)-1, -1, -1):# 뒤에서 부터 
        if S[j] == '0':
            S.pop(j)
            break

for i in range(len(one_arr) // 2): # 반절
    for j in range(0, len(S), 1):# 앞에서 부터 
        if S[j] == '1':
            S.pop(j)
            break

for i in S:
    print(i, end="")

시간복잡도

O(n^2)

입력

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

출력

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

예제 입력


1010

00110000

예제 출력


01

0010

알고리즘 분류

문자열

그리디 알고리즘