월간 코드 챌린지 시즌2: 110 옮기기

https://programmers.co.kr/learn/courses/30/lessons/77886

코딩테스트 연습 - 110 옮기기

 

파이썬

일단 개념을 제대로 잡았는 지 전수조사(brute force)로 확인... 

def solution(s):
    return [move110(num) for num in s]


def move110(num: str) -> str:
    index = num.find('110')
    if index == -1:
        return num
    num = num[:index] + num[index + 3:]
    first, first_index = '110' + num, 3
    for index in range(1, len(num)):
        temp = num[:index] + '110' + num[index:]
        if first > temp:
            first = temp
            first_index = index + 3
    return first[:first_index] + move110(first[first_index:])

헉 다 틀림... 

테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	실패 (시간 초과)
테스트 6 〉	실패 (시간 초과)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	실패 (275.90ms, 30MB)
테스트 10 〉	실패 (315.40ms, 31.7MB)
테스트 11 〉	실패 (342.93ms, 30.7MB)
테스트 12 〉	실패 (323.19ms, 30.7MB)
테스트 13 〉	실패 (337.03ms, 30.2MB)
테스트 14 〉	실패 (376.10ms, 30.1MB)
테스트 15 〉	실패 (354.40ms, 30.2MB)
테스트 16 〉	실패 (337.44ms, 30.1MB)
테스트 17 〉	실패 (303.78ms, 29MB)
테스트 18 〉	실패 (시간 초과)
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	실패 (시간 초과)
테스트 21 〉	실패 (시간 초과)

문제에 제시된 해법 그대로 풀었는데...

110을 뽑은 뒤
(모든 경우) 삽입한 뒤,
가장 앞선 것을 확인하고,
정렬이 끝난 부분 뒤는 다시 반복...

질문 목록에서 장재준님의 글을 보니
'우선 문자열에서 "110"이 모두 없어질 때까지 뽑습니다.'

다시 문제를 보니... 
"그림에 나온 방식 말고도 다른 방법으로 "0110110111"을 만들 수 있습니다."

--;;;

깔끔한 문제는 아닌 것 같다. 

코드를 수정해서 다시 확인... 

def solution(s):
    return [insert110(*remove110(num)) for num in s]


def remove110(num, count=0):
    index = num.find('110')
    if index == -1:
        return num, count
    return remove110(num[:index] + num[index + 3:], count + 1)


def insert110(num, count):
    if count == 0:
        return num
    first, first_index = '110' + num, 3
    count -= 1
    for index in range(1, len(num) + 1):
        temp = num[:index] + '110' + num[index:]
        if first > temp:
            first = temp
            first_index = index + 3
    return first[:first_index] + insert110(first[first_index:], count)

테스트 1 〉	실패 (런타임 에러)
테스트 2 〉	실패 (런타임 에러)
테스트 3 〉	실패 (런타임 에러)
테스트 4 〉	실패 (런타임 에러)
테스트 5 〉	실패 (런타임 에러)
테스트 6 〉	실패 (런타임 에러)
테스트 7 〉	실패 (런타임 에러)
테스트 8 〉	실패 (런타임 에러)
테스트 9 〉	통과 (255.42ms, 30MB)
테스트 10 〉	통과 (287.08ms, 31.7MB)
테스트 11 〉	통과 (259.98ms, 30.8MB)
테스트 12 〉	통과 (297.91ms, 30.6MB)
테스트 13 〉	통과 (278.86ms, 30MB)
테스트 14 〉	통과 (263.22ms, 30.2MB)
테스트 15 〉	통과 (295.80ms, 30.2MB)
테스트 16 〉	통과 (318.25ms, 30.1MB)
테스트 17 〉	통과 (294.85ms, 29.1MB)
테스트 18 〉	실패 (런타임 에러)
테스트 19 〉	실패 (런타임 에러)
테스트 20 〉	실패 (런타임 에러)
테스트 21 〉	실패 (런타임 에러)

대략 개념은 이해한 것 같고.. 

재귀 때문에 런타임 에러가 나온 것 같으니...
재귀를 반복문으로 바꿔야 할 듯...

def solution(s):
    return [insert110(*remove110(num)) for num in s]


def remove110(num):
    count = 0
    while (index := num.find('110')) != -1:
        num = num[:index] + num[index + 3:]
        count += 1
    return num, count


def insert110(num, count):
    answer = ''
    while count != 0:
        count -= 1
        first_str, first_index = '110' + num, 3
        for index in range(1, len(num) + 1):
            temp = num[:index] + '110' + num[index:]
            if first_str > temp:
                first_str = temp
                first_index = index + 3
        answer += first_str[:first_index]
        num = first_str[first_index:]
    answer += num
    return answer

예상과 같이...
이제 시간만(?) 줄이면 된다. 

테스트 1 〉	통과 (2174.80ms, 15.7MB)
테스트 2 〉	통과 (6825.23ms, 15.6MB)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	통과 (1562.92ms, 15.7MB)
테스트 6 〉	통과 (5121.17ms, 15.6MB)
테스트 7 〉	실패 (시간 초과)
테스트 8 〉	실패 (시간 초과)
테스트 9 〉	통과 (298.28ms, 29.9MB)
테스트 10 〉	통과 (370.13ms, 31.8MB)
테스트 11 〉	통과 (259.27ms, 30.6MB)
테스트 12 〉	통과 (282.55ms, 30.7MB)
테스트 13 〉	통과 (276.45ms, 30MB)
테스트 14 〉	통과 (264.67ms, 30MB)
테스트 15 〉	통과 (291.32ms, 30.1MB)
테스트 16 〉	통과 (303.94ms, 30.2MB)
테스트 17 〉	통과 (348.93ms, 29.1MB)
테스트 18 〉	실패 (시간 초과)
테스트 19 〉	실패 (시간 초과)
테스트 20 〉	실패 (시간 초과)
테스트 21 〉	실패 (시간 초과)

 

시간을 줄여야하니 먼저 remove011 함수를 개선해 보자.. 
find 메소드의 경우 매번 문자열의 처음부터 '110'을 검색한다.
필요없는 부분까지 검색 범위에 포함되어 효율성이 떨어진다. 
이는 stack을 이용하면 최적화 할 수 있다. 

def solution(s):
    return [insert110(*remove110(num)) for num in s]


def remove110(num):
    count, stack = 0, []
    for each in num:
        if each == '0' and len(stack) >= 2 and stack[-1] == stack[-2] == '1':
            stack.pop()
            stack.pop()
            count += 1
        else:
            stack.append(each)
    return ''.join(stack), count


def insert110(num, count):
    answer = ''
    while count != 0:
        count -= 1
        first_str, first_index = '110' + num, 3
        for index in range(1, len(num) + 1):
            temp = num[:index] + '110' + num[index:]
            if first_str > temp:
                first_str = temp
                first_index = index + 3
        answer += first_str[:first_index]
        num = first_str[first_index:]
    return answer + num

본론은 시작도 안했는데... 
꽤 좋아졌다.. 
테스트 4를 제외하고 모두 통과

테스트 1 〉	통과 (643.35ms, 15.6MB)
테스트 2 〉	통과 (1156.74ms, 15.6MB)
테스트 3 〉	통과 (2690.97ms, 14.4MB)
테스트 4 〉	실패 (시간 초과)
테스트 5 〉	통과 (470.27ms, 15.7MB)
테스트 6 〉	통과 (566.98ms, 15.7MB)
테스트 7 〉	통과 (926.81ms, 14.1MB)
테스트 8 〉	통과 (980.14ms, 13MB)
테스트 9 〉	통과 (349.50ms, 30.4MB)
테스트 10 〉	통과 (366.25ms, 31.9MB)
테스트 11 〉	통과 (355.53ms, 30.7MB)
테스트 12 〉	통과 (390.37ms, 30.9MB)
테스트 13 〉	통과 (372.59ms, 30.4MB)
테스트 14 〉	통과 (400.53ms, 30.1MB)
테스트 15 〉	통과 (393.03ms, 30.1MB)
테스트 16 〉	통과 (440.80ms, 30.1MB)
테스트 17 〉	통과 (341.25ms, 29.1MB)
테스트 18 〉	통과 (212.55ms, 14.5MB)
테스트 19 〉	통과 (255.42ms, 16.9MB)
테스트 20 〉	통과 (194.17ms, 14.2MB)
테스트 21 〉	통과 (239.26ms, 16.4MB)

insert110 함수를 개선해 보자.. 

테스트 결과들을 보면
문자열의 끝에서 역순으로 '0'을 검색해서
'0' 뒤에 '110'을 삽입하면 된다는 것을 알 수 있다.   

def solution(s):
    return [insert110(*remove110(num)) for num in s]


def remove110(num):
    count, stack = 0, []
    for each in num:
        if each == '0' and len(stack) >= 2 and stack[-1] == stack[-2] == '1':
            stack.pop()
            stack.pop()
            count += 1
        else:
            stack.append(each)
    return ''.join(stack), count


def insert110(num, count):
    index = num[::-1].find('0')
    if index == -1:
        return '110' * count + num
    else:
        index = len(num) - index
        return num[:index] + '110' * count + num[index:]

테스트 1 〉	통과 (181.95ms, 15.6MB)
테스트 2 〉	통과 (128.57ms, 15.5MB)
테스트 3 〉	통과 (99.13ms, 14.3MB)
테스트 4 〉	통과 (139.25ms, 16.7MB)
테스트 5 〉	통과 (139.07ms, 15.7MB)
테스트 6 〉	통과 (134.46ms, 15.6MB)
테스트 7 〉	통과 (90.48ms, 14.3MB)
테스트 8 〉	통과 (78.96ms, 13.1MB)
테스트 9 〉	통과 (184.53ms, 30.4MB)
테스트 10 〉	통과 (166.92ms, 32MB)
테스트 11 〉	통과 (191.70ms, 30.9MB)
테스트 12 〉	통과 (170.15ms, 30.9MB)
테스트 13 〉	통과 (196.10ms, 30.5MB)
테스트 14 〉	통과 (174.89ms, 30.2MB)
테스트 15 〉	통과 (166.43ms, 30.1MB)
테스트 16 〉	통과 (192.34ms, 30.1MB)
테스트 17 〉	통과 (160.39ms, 29.1MB)
테스트 18 〉	통과 (128.81ms, 14.5MB)
테스트 19 〉	통과 (144.47ms, 16.9MB)
테스트 20 〉	통과 (106.81ms, 15.1MB)
테스트 21 〉	통과 (121.57ms, 16.4MB)

함수 하나로....

그런데 리스트에는 find 메소드가 없어서... 코드가 이쁘게 안나옴.. 
count는 무조건 한바퀴 돌아 버리니... 

def solution(s):
    return [move110(num) for num in s]


def move110(num):
    count, stack = 0, []
    for each in num:
        if each == '0' and len(stack) >= 2 and stack[-1] == stack[-2] == '1':
            del stack[-2:]
            count += 1
        else:
            stack.append(each)
    if stack.count('0') == 0:
        return ''.join(['1', '1', '0'] * count + stack)
    else:
        index = len(stack) - stack[::-1].index('0')
        return ''.join(stack[:index] + ['1', '1', '0'] * count + stack[index:])

테스트 1 〉	통과 (185.58ms, 15.5MB)
테스트 2 〉	통과 (150.82ms, 15.5MB)
테스트 3 〉	통과 (128.40ms, 18.2MB)
테스트 4 〉	통과 (168.32ms, 33.6MB)
테스트 5 〉	통과 (198.75ms, 15.7MB)
테스트 6 〉	통과 (165.45ms, 15.9MB)
테스트 7 〉	통과 (110.87ms, 20.4MB)
테스트 8 〉	통과 (110.32ms, 20.2MB)
테스트 9 〉	통과 (201.57ms, 30.5MB)
테스트 10 〉	통과 (205.11ms, 32.2MB)
테스트 11 〉	통과 (232.38ms, 30.7MB)
테스트 12 〉	통과 (244.49ms, 30.9MB)
테스트 13 〉	통과 (221.54ms, 30.3MB)
테스트 14 〉	통과 (206.78ms, 30MB)
테스트 15 〉	통과 (242.37ms, 30MB)
테스트 16 〉	통과 (204.56ms, 30.1MB)
테스트 17 〉	통과 (155.11ms, 29.1MB)
테스트 18 〉	통과 (115.46ms, 17.1MB)
테스트 19 〉	통과 (138.40ms, 29.1MB)
테스트 20 〉	통과 (121.97ms, 17.9MB)
테스트 21 〉	통과 (134.48ms, 29MB)

일일히 검사함...

def solution(s):
    return [move110(num) for num in s]


def move110(num):
    count, stack = 0, []
    for each in num:
        if each == '0' and len(stack) >= 2 and stack[-1] == stack[-2] == '1':
            del stack[-2:]
            count += 1
        else:
            stack.append(each)
    index = -1
    for i, number in enumerate(stack[::-1]):
        if number == '0':
            index = i
            break
    if index == -1:
        return ''.join(['1', '1', '0'] * count + stack)
    else:
        index = len(stack) - index
        return ''.join(stack[:index] + ['1', '1', '0'] * count + stack[index:])

테스트 1 〉	통과 (150.67ms, 15.6MB)
테스트 2 〉	통과 (140.07ms, 15.6MB)
테스트 3 〉	통과 (131.49ms, 18.2MB)
테스트 4 〉	통과 (212.69ms, 33.7MB)
테스트 5 〉	통과 (139.69ms, 15.6MB)
테스트 6 〉	통과 (137.44ms, 15.9MB)
테스트 7 〉	통과 (103.30ms, 20.4MB)
테스트 8 〉	통과 (81.82ms, 20.2MB)
테스트 9 〉	통과 (186.82ms, 30.5MB)
테스트 10 〉	통과 (204.67ms, 32.1MB)
테스트 11 〉	통과 (191.17ms, 30.7MB)
테스트 12 〉	통과 (183.06ms, 30.6MB)
테스트 13 〉	통과 (177.44ms, 30.4MB)
테스트 14 〉	통과 (183.57ms, 30.2MB)
테스트 15 〉	통과 (175.30ms, 30.2MB)
테스트 16 〉	통과 (172.77ms, 30.2MB)
테스트 17 〉	통과 (167.02ms, 29MB)
테스트 18 〉	통과 (122.36ms, 17.1MB)
테스트 19 〉	통과 (132.82ms, 29.1MB)
테스트 20 〉	통과 (112.60ms, 17.9MB)
테스트 21 〉	통과 (156.70ms, 29.1MB)