[문자열/백준] 20310번 : 타노스

- 문제 : https://www.acmicpc.net/problem/20310

 

문제 이해 

- 0과 1로만 이루어져있고, 각 숫자가 모두 짝수개만 존재하는 문자열 하나가 주어진다.

 

- 각 숫자를 절반 개수만큼 지웠을 때 가장 작은 숫자를 출력하는 문제다. 

 

- 처음에는 0 절반 + 1 절반 붙여서 출력하면 되지 않나?라고 생각했지만, 주어진 문자의 순서를 모두 지켜야 했다. 그래서 생각한 방법이 숫자가 가장 작아지려면 0이 최대한 앞에 있어야하고, 1은 최대한 뒤에 있어야 한다는 것이었다. 

 

- 그래서 주어진 단어를 왼쪽에서부터 진행하면서 0의 경우는 전체 0의 개수의 절반만큼 0을 왼쪽부터 찾고, 1의 경우는 전체 1의 개수의 절반만큼을 왼쪽에서 지운 뒤 나머지 절반을 뒤에 남기는 것이었다. 

 

풀이 로직 

- 숫자를 리스트로 변형한 뒤 전체 0의 개수의 절반을 zero, 전체 1의 개수의 절반을 one에 저장한다.

- number에서 가장 왼쪽 수를 pop한다.

- 숫자가 1인 경우는 one의 값이 0이하일 때만 answer에 추가하고, 아직 없애야할 1의 개수가 남아있는 경우(one > 0)에는 one -= 1만 한다. 

- 숫자가 0인 경우는 zero > 0 일 때만 answer에 추가하고, 아니라면 넘어간다. 

- 이렇게 만든 answer의 원소들을 하나의 문자열로 출력한다. 

 

 

정답 풀이 

number = list(input())

zero = number.count('0') // 2
one = number.count('1') // 2

answer = []
while number:
    x = number.pop(0)
    
    if x == '1':
        if one <= 0 :
            answer.append(x)
        else:
            one -= 1
    else:
        if zero > 0:
            answer.append(x)
            zero -= 1
            
print(''.join(answer))