[백준 20310 / Python / 실버3] 타노스

문제

 

그리디 문제이다. 실버 3보다는 좀 더 쉬운 것 같다. 시간복잡도도 고려할 필요 없다. 난 고려하긴 했지만.

 

import sys

input = sys.stdin.readline

"""

0이 앞에 최대한 많아야 한다

1은 앞부터 지우고

0은 뒤부터 지우면 되지않나

1. 리스트로 받아서 , 지우지 말고 -1로 교체 (지우는 연산 오버헤드 방지)

2. 앞부터 -1이 아닐 경우 출력

"""

S = list(map(int, input().strip()))

"""0, 1 개수 세기"""

count = [0] * 2  # 0의 개수, 1의 개수 저장할 리스트

for num in S:

    if num == 0:

        count[0] += 1

    else:

        count[1] += 1

"""앞부터 1 지우기"""

deleted_one = 0

for i in range(len(S)):

    if S[i] == 1:

        S[i] = -1

        deleted_one += 1

    if deleted_one >= (count[1] // 2):

        break

"""뒤부터 0 지우기"""

deleted_zero = 0

for i in range(len(S) - 1, -1, -1):

    if S[i] == 0:

        S[i] = -1

        deleted_zero += 1

    if deleted_zero >= (count[0] // 2):

        break

result = ''.join(str(x) for x in S if x != -1)

print(result)

 

1과 0을 절반씩 지우되, 그 결과 중 사전순으로 가장 앞에 오는 것을 출력하면 된다.

이게 무슨 의미냐면, 결과 중 가장 작은 수를 출력하면 된다는 의미이고,

앞쪽부터 최대한 많은 0이 연속되어야 한다는 뜻이다. 0은 최대한 앞에, 1은 최대한 뒤에 있어야 한다. 

따라서 나는 1은 앞부터, 0은 뒤부터 지우면 이 조건을 만족할 수 있을 거라 생각했다.

 

우선 지울 0과 1의 개수부터 구한 후에 2번의 반복문을 통해 1과 0을 각각 앞부터, 뒤부터 지워 줬다.

근데 여기서 실제 리스트를 변경하지 않았다. 지우는 연산 remove 또는 pop함수의 오버헤드 때문에 최악 시간복잡도가 O(N^2) 까지 갈 수 있기 때문이다. 

 

그래서 실제로 리스트를 변경하지 않고 -1로 변경함으로써 지우는 효과만 내도록 했다.

그리고 마지막 출력할 땐 -1을 제외하고 하나의 문자열로 변경하여 출력해 주었다.

 

이렇게 하면 remove나 pop을 사용했을 때 O(N^2) 에서, 정확히 O(4N)의 시간복잡도로 개선된다.

지울 0과 1 개수 세기 -> O(N)

1 지우기 -> O(N)

0 지우기 -> O(N)

결과 문자열로 변경 -> O(N)

이렇게 총 O(4N) 이며, 상수를 제외하면 O(N)에 수렴하게 된다.

 

결과

 

이 문제의 입력값 길이는 최대 500으로써, 길이가 길지 않아 O(N^2)도 통과되긴 한다. 그러나 지금 상태로도 N^2 코드에 비해 내 코드가 약 3배 정도 빠르다. 입력 길이가 더 길어진다면 그 차이는 더욱 커질 것이다.