[Programmers]77886. 110 옮기기

77886. 110 옮기기

❌ code1

def solution(s):
    answer = []

    for x in s:
        count = 0  # 만들 수 있는 110의 개수
        result = []  # 110을 제외한 나머지 숫자들

        # x에서 만들 수 있는 110을 모두 제거
        for number in x:
            result.append(number)
            if 3 <= len(result) and result[-3:] == ["1", "1", "0"]:
                count += 1
                result = result[: -3]

        for index in range(len(result) - 1, -1, -1):  # 110을 제거한 결과를 역순으로 탐색
            if result[index] == "0":  # 0을 만나는 순간 0 뒤로 110을 전부 추가
                answer.append("".join(result[0: index + 1])
                              + "110" * count + "".join(result[index + 1:]))
                break
        else:  # 0이 없는 경우 맨 앞에 110을 전부 추가
            answer.append("110" * count + "".join(result))

    return answer

시도

1. 문자열 x에서 "110"을 제거하고, 제거한 결과에서 계속 반복하여 "110"을 제거한다.
2. 남은 문자열 x를 역으로 탐색해 가장 먼저 "0"을 만나는 지점을 구한 뒤, 그 뒤에 제거했던 "110"을 모두 추가한다.
   1. 만약 "0"이 없다면 맨 앞에 제거했던 "110"을 모두 추가한다.

문제

시간 초과.

⭕ code2

def solution(s):
    answer = []

    for x in s:
        count = 0  # 만들 수 있는 110의 개수
        result = []  # 110을 제외한 나머지 숫자들

        # x에서 만들 수 있는 110을 모두 제거
        for number in x:
            result.append(number)
            if 3 <= len(result) and result[-3:] == ["1", "1", "0"]:
                count += 1
                result.pop()
                result.pop()
                result.pop()

        for index in range(len(result) - 1, -1, -1):  # 110을 제거한 결과를 역순으로 탐색
            if result[index] == "0":  # 0을 만나는 순간 0 뒤로 110을 전부 추가
                answer.append("".join(result[0: index + 1])
                              + "110" * count + "".join(result[index + 1:]))
                break
        else:  # 0이 없는 경우 맨 앞에 110을 전부 추가
            answer.append("110" * count + "".join(result))

    return answer

시도

기존에는 문자열 x에 존재하는 "110"을 제거할 때 "110"을 발견한 경우 마지막 세 개의 원소를 제거해야 하므로 slicing을 이용했다. 하지만 여기서 시간이 오래 소요되어 slicing 대신 pop() 메서드를 사용한다.

pop() 메서드는 O(1)의 시간 복잡도를 갖는 반면 slicing을 이용하는 경우 result[: -3]라는 새로운 리스트를 생성한 뒤 이를 result에 할당하는 과정을 거쳐 O(n)의 시간 복잡도를 갖는다.

요약

리스트 slicing은 O(n)의 시간 복잡도를 갖기 때문에 마지막 원소만을 리스트에서 제거하고자 할 때는 pop() 메서드를 사용하는 것이 더 효과적이다.