[Python] 프로그래머스 / 월간 코드 챌린지 시즌2 / 110 옮기기

문제 링크

 

시간복잡도 초과된 코드 

이 코드는 시퀀스에서 "110"을 찾아서 다른 데에 끼워넣을 수 있는 모든 경우의 수를 찾고, 그중 사전순 가장 빠른 시퀀스를 찾아서, 다시 그 시퀀스에서 "110"을 찾고...를 반복하는 코드이다. 

def solution(s):
    answer = []
    
    for sequence in s :
        n = len(sequence)
        if n < 4 :
            answer.append(sequence)
            break
    
        while True :
            candidate = []
            for i in range(n-2) :
                if sequence[i:i+3] == "110" :
                    candidate.append(i)
            if not candidate :
                break
            
            new_sequences = []
            for i in candidate :
                new_sequence = sequence[:i] + sequence[i+3:]
                for j in range(n-2) :
                    new_sequences.append(new_sequence[:j] + "110" + new_sequence[j:])
                    
            if sequence == min(new_sequences) :
                break
            
            sequence = min(new_sequences)
        answer.append(sequence)
    return answer

 

 

Stack 자료구조를 이용해 새롭게 탄생될 "110"을 미리 감지하기

관건은 뭐였냐면, "110"을 전부 찾아서 다른 데에 옮겼는데 그걸 옮김으로 인해서 그 전에 없었던 새로운 "110"이 생기면 그것을 어떻게 처리하는가였다. 답은 생각보다 간단했는데, stack 자료구조를 이용하는 것이었다.

위와 같이 빨간 110을 제거해서 다른 데로 옮기면 전에는 없었던 새로운 110이 탄생한다. (파란 110)

 

 

그런데 위와 같이 110을 1 뒤로 옮길 수는 없다. 그러면 ...111010이었던 것이 ...111100이 되어버려 오히려 사전 순으로 늦어지기 때문에, 문제의 방침에 맞지 않다.

 

즉, 위의 경우에 새로운 110의 탄생은 필연적이다.

 

 

그러므로 시퀀스의 숫자들을 계속 stack에 쌓아가다가 0이 발견되면 stack 맨 뒤의 두 숫자를 탐지해 그게 "11"이면 stack에서 제거하면, 새롭게 탄생될 110을 미리미리 감지할 수 있다. 즉, 불필요한 loop의 사용이 없어진다.

 

맨 오른쪽에 있는 0 뒤에 110 끼워넣기 (0이 없다면 맨 앞에 삽입하기)

110을 찾았다면 어디로 옮기는 게 사전순 최선일까를 찾기 위해 탐색할 필요는 없다. 일단 110을 다 빼버렸는데 0은 없고 1만 남았다면, 당연히 맨 앞에 110을 갖다 붙이면 된다. 그러지 않고 110을 다 빼버렸는데 0과 1이 섞여있다면, 그냥 맨 뒤에 나오는 0 뒤에 끼워넣으면 된다. 왜냐하면 110은 0과 1이 만들어낼 수 있는 세자리 시퀀스 중, 가장 사전순으로 마지막에 위치한 것이기 때문이다.

 

정답코드

def solution(s):
    answer = []
    
    for string in s :
        cnt = 0
        stack = ''
        idx = 0
        
        while idx < len(string) :
            if string[idx] == "0" and stack[-2:] == "11" :
                stack = stack[:-2]
                cnt += 1
            else :
                stack += string[idx]
            idx += 1

        if cnt == 0 :
            answer.append(string)
            continue
        
        new_place = stack.rfind("0") 
        if new_place == -1 :
            new_string = "110" * cnt + stack
            
        else :
            new_string = stack[:new_place+1] + "110" * cnt + stack[new_place+1:]
            
        answer.append(new_string)
        
    return answer