[백준/20310] 타노스 (Python)

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

20310번: 타노스

 

Difficulty : Silver 3

 

Status : Solved

 

Time : 00:06:38

 

---

 

문제 설명

 

 

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

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

 

 

입력 및 출력

 

입력

 

문자열 S가 주어진다.

 

출력

 

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

 

입력 예시

 

000011

 

출력 예시

 

001

 

 

---

 

풀이

 

간단하게 그리디로 접근 가능한 문제이다. 잘 생각해보면 같은 위치의 1, 0 중 0이 사전적으로 앞서므로 0은 가급적 앞에, 1은 가급적 뒤에 남아 있는게 좋다. 즉 0은 오른쪽부터 왼쪽으로 탐색하며 절반을 제거하고, 1은 왼쪽부터 오른쪽으로 탐색하며 절반을 제거하면 사전순으로 가장 앞서는 문자열을 남길 수 있다.

 

풀이 코드

S = list(input().strip())

ones, zeros = 0, 0
for s in S :
  if s == '0' :
    zeros += 1
  else :
    ones += 1

ones //= 2
zeros //= 2
idx = len(S) - 1
while zeros :
  if S[idx] == '0' :
    S.pop(idx)
    zeros -= 1
  idx -= 1

idx = 0
while ones :
  if S[idx] == '1' :
    S.pop(idx)
    ones -= 1
  else :
    idx += 1

print(''.join(S))

풀이 완료!