220317 - 110 옮기기

◾ 110 옮기기 : 프로그래머스 LEVEL 3

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

문제

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의 개수를 확인하고 최적의 자리에 추가해준다.
  • 1110 -> 1101, 0110 -> 0110
  • 위와 같이 1인 경우 110이 앞으로 0인 경우 110이 뒤에 위치해야 사전순으로 빠르게 정렬된다.
• 참고 : https://davi06000.tistory.com/76

---

2. 프로그램

1. 문자열에서 110의 개수 추출
   • 스택 구조를 통해 문자를 하나씩 추가한다.
   • 110이 나오는 경우 해당 값은 삭제하고 개수를 체크한다.
   • 110을 삭제한 문자열과 110의 개수를 반환한다.
2. 110 재배치
   • 문자열의 뒤부터 검사하여 0이 나오는 인덱스를 찾는다. (해당 인덱스를 i라 가정한다.)
   • 해당 자리에 모든 110이 연속으로 배치된다.
   • 따라서, 110을 해당 위치에 개수만큼 추가해준다.

# 코드
def solution(s):
    answer = []

    def extract(s):
        count, stack = 0, []
        for word in s:
            if word == '0' and stack[-2:] == ['1', '1']:
                stack.pop()
                stack.pop()
                count += 1
            else:
                stack.append(word)
        return ''.join(stack), count

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

    answer = []
    for _s in s:
        _s, count = extract(_s)
        _s = rearrange(_s, count)
        answer.append(_s)

    return answer