[프로그래머스/LV3] 110 옮기기 (Python)

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

프로그래머스

 

Status : Solved

 

Time : 00:09:26

 

---

 

문제 설명

 

0과 1로 이루어진 어떤 문자열 x에 대해서, 당신은 다음과 같은 행동을 통해 x를 최대한 사전 순으로 앞에 오도록 만들고자 합니다.

• x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.

예를 들어, x = "11100" 일 때, 여기서 중앙에 있는 "110"을 뽑으면 x = "10" 이 됩니다. 뽑았던 "110"을 x의 맨 앞에 다시 삽입하면 x = "11010" 이 됩니다.

변형시킬 문자열 x가 여러 개 들어있는 문자열 배열 s가 주어졌을 때, 각 문자열에 대해서 위의 행동으로 변형해서 만들 수 있는 문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

입력 및 출력

 

제한사항

• 1 ≤ s의 길이 ≤ 1,000,000
• 1 ≤ s의 각 원소 길이 ≤ 1,000,000
• 1 ≤ s의 모든 원소의 길이의 합 ≤ 1,000,000

 

입출력 예

s	result
["1110","100111100","0111111010"]	["1101","100110110","0110110111"]

 

 

---

 

풀이

 

그리디로 접근하면 쉬운 문제. 크게 두 가지가 요구된다.

 

1. 가능한 모든 110을 뽑아내기 :  문자열 전체를 순회하며, 순회하는 문자열을 스택에 저장한다. 스택의 맨 위 세 글자가 '110'이 아닐 때까지, 스택의 세 원소를 제거하고 110을 카운트한다. 이런 식으로 문자열 내에 원래 존재하는 110 및 이를 제거하였을 때 만들어질 수 있는 모든 110을 카운트할 수 있다.

 

2. 110 집어넣기 : 이 방법은 그리디를 사용하는 것이 가장 쉽다. 그리디로 접근한다면, 우리는 그 구체적인 전략을 정해야 한다. 이 문제에서는 카운트한 모든 110을 어디에 집어넣을지 여부를 결정한다. 결론을 먼저 말하자면, '가장 마지막에 나오는 0 바로 뒤에 모든 110을 삽입한다'가 되겠다.

• 모든 110을 제거했으므로, 남은 문자열에는 0 사이에 최대 1개의 1이 존재할 수 있다. 2개 이상의 1이 존재할 경우, 존재할 수 없는 110 패턴이 나오게 되므로 모순이 된다.
• 가장 마지막에 나오는 0이 존재한다고 가정하고, 그 다음 문자에 나올 수 있는 경우의 수는 '0111....'이 된다. 즉 0 뒤에 0개 이상의 1이 문자열의 끝까지 존재한다. 이후에 0은 나올 수 없기 때문이다. 이 위치에 110이 들어가게 되면 '0' + '110110...' + '111...'꼴이 되어 사전 순으로 앞서게 된다.
  • 이 뒤의 1에 110을 삽입하더라도, 앞의 경우보다 사전순으로 뒤에 오게 된다.
• 그 이전의 0에 110을 연결하는 경우를 생각해 보자. 바로 뒤에 0이 오는 경우와 1이 오는 경우, 두 가지 경우가 발생한다.
  • 00 : 이 경우, 110을 삽입하게 되면 01100xx..꼴이 되므로 오히려 사전 순으로 뒤로 밀려난다.
  • 0100, 0101 : 앞선 제약 조건 때문에, 1 바로 뒤에는 0이 올 수밖에 없다. 이 경우 삽입 후에는 0110100, 0110101꼴이 된다. 100, 101 모두 사전순으로 110보다 앞서므로 오히려 사전 순으로 뒤로 밀려난다.
• 만약 0이 존재하지 않는다면, 110이 맨 앞에 오도록 하면 사전순으로 가장 앞서게 된다.

 

 

풀이 코드

from collections import deque

def find_110s(s) :
    stk = ''
    cnt = 0
    
    for _s in s :
        stk += _s
        while len(stk) > 2 and stk[-3:] == '110' :
            stk = stk[:-3]
            cnt += 1
    
    return stk, cnt

def insert_110s(s, cnt) :
    length = len(s)
    
    for i in range(length-1, -1, -1) :
        if s[i] == '0' :
            return s[:i+1] + '110'*cnt + s[i+1:]
        
    return '110'*cnt + s

def solution(s):
    answer = []
    for _s in s :
        stk, cnt = find_110s(_s)
        answer.append(insert_110s(stk, cnt))
    
    return answer

풀이 완료~