💡문제접근
- 문자열 S에 나타나는 0과 1의 빈도의 절반만큼 지워줘야한다.
- 이 때 주의할 점은 S'로 가능한 문자열 중 사전순으로 가장 빠른 것을 구해야 한다는 것이다. 나는 그냥 별 생각없이
sort()를 사용했는데 바로 WA를 받았다.- 질문게시판에 있는 내용 중에서 하나 도움이 되는 내용이 있어서 이 내용을 참고했다.
- 사전순으로 가장 빠른 문자열을 출력해야하고 이 때, 자리를 재배치할 수 없다.
📌 테스트케이스
입력
00110000
출력
0010
- 사전순으로 가장 빠른 문자열을 배치하려면 0이 먼저 나와 있어야 하고 1이 최대한 뒤늦게 나와야 한다. 따라서 0은 뒤에서부터 제거하고 1은 앞에서부터 제거하면 원하는 결과를 얻을 수 있다.
💡코드(메모리 : 31256KB, 시간 : 40ms)
import sys
input = sys.stdin.readline
S = list(input().strip())
cnt_0 = S.count("0") // 2
cnt_1 = S.count("1") // 2
for i in range(cnt_0):
S.pop(-S[::-1].index("0")-1)
for i in range(cnt_1):
S.pop(S.index("1"))
print(''.join(map(str, S)))💡소요시간 : 24m
🐢