문제 설명 및 제한사항
문제 설명
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
아이디어 및 해결 방법
문제를 해결하기 위해서 중요한 관찰은, 110을 문자열에 삽입해서 새로 110이 나타나는 경우가 없다는 것입니다.
맨 앞이나 맨 뒤에 들어갔을 때는 자명하게 110이 새로 나타날 수가 없고, 아래와 같이 임의의 두 숫자 사이에 들어가는 경우의 수 4가지를 모두 고려해보아도 그렇습니다.
0 110 0 # 0과 0 사이에 들어가는 경우
0 110 1 # 0과 1 사이에 들어가는 경우
1 110 0 # 1과 0 사이에 들어가는 경우
1 110 1 # 1과 1 사이에 들어가는 경우
Python
복사
즉, 이 관찰에 의해서 문자열에서 나타나는 110들을 모두 제거한 다음, 110을 채워넣는 식으로 진행해도 제거-삽입을 섞어서 진행하는 방식과 동일한 결과를 반드시 얻을 수 있다는 것을 알 수 있습니다.
이제 (1) 110을 모두 제거하고, (2) 최적의 배치로 110을 채워넣는 순서로 문제를 단순화해서 풀 수 있겠네요!
110을 모두 제거하는 방법
스택 하나를 관리합니다. 문자열을 앞에서부터 읽어가면서 숫자를 하나하나 스택에 push합니다.
이때, 스택의 맨 위부터 3개의 숫자를 각각 가리키는 포인터 3개를 관리하면서, 110이 발견되면 110을 바로 제거한 뒤 발견한 110의 개수를 1개 증가시킵니다.
이 과정을 마지막 숫자까지 반복하면 모든 110을 제거할 수 있음과 동시에 110을 제거하고 남은 숫자의 배열을 얻게 됩니다.
빼둔 110들을 넣어서 사전 순으로 가장 앞에 오는 문자열을 만드는 방법
110을 어떻게 넣어야 사전 순으로 가장 앞에 오는 문자열을 만들 수 있을까요? 우선 단순하게 110 한 개가 있는 경우를 생각해봅시다.
110보다 사전 순으로 뒤에 있는 세 자리 수는 111밖에 없습니다. 따라서 110이 들어가서 사전 순으로 더 앞으로 가는 경우는, 111이 있던 자리에 110이 끼어들어가는 경우밖에 없는 것이지요!
그렇다면 문자열의 111들 중 어떤 111 위치에 들어가야 가장 유리할까요? 가장 자리수가 큰 (가장 왼쪽에 있는) 111일 것입니다.
가장 왼쪽의 111은 어떻게 찾을 수 있을까요? 바로 오른쪽부터 읽어가며 처음 등장하는 0을 찾는 것입니다. 그러한 0을 찾으면 그 왼쪽에는 111이 없다는 것이 보장되기 때문입니다. 왜 그럴까요?
110을 넣을 문자열에는 110이 모두 제거되어 있다는 사실을 떠올리면 이해가 됩니다.
증명) ‘오른쪽부터 찾았을 때 처음 나타나는 0’의 왼쪽에 111이 또 있다고 가정해봅시다. 이 문자열에는 110이 없어야 하므로, 그 111 뒤에는 0이 올 수 없습니다. 따라서 111 뒤에는 1이 오게 되는데, 이 논리가 반복되면 결국 우리가 찾은 0의 바로 앞까지 1로 채워져 있어야 한다는 의미가 됩니다. 그렇다면 ….110 의 형태가 만들어지고, 110이 없다는 전제에 위배됩니다.
따라서 오른쪽부터 찾았을 때 처음 나타나는 0 뒤에 110을 끼워넣으면 해결됩니다.
이제 110이 여러개인 상황으로 일반화해봅시다. 일반적인 상황에서 110을 위와 같이 하나 넣은 상태를 생각해보면, …01101111…의 형태가 될 것입니다. 110의 삽입은 새로운 111을 만들지 않으므로, 그냥 방금 넣은 110 뒤에 110을 넣는 것이 최선임을 쉽게 알 수 있습니다. 따라서, 110이 여러개인 상황에서도, ‘오른쪽부터 찾았을 때 처음 나타나는 0’의 뒤에 110 x n 을 삽입하는 식으로 해결 가능합니다.
예외 상황으로서, 만약 오른쪽부터 찾았을 때 0이 발견되지 않는다면, 문자열의 가장 왼편에 110 x n을 삽입하는 것이 최선임을 알 수 있습니다. 잘 처리해줍시다!
코드
def solution(s):
# 110을 새로 넣어서 110이 나타나는 경우가 있을까요? 없습니다.
# 0 110 0
# 0 110 1
# 1 110 0
# 1 110 1
# 따라서 문자열에서 110이 나타날 때마다 제거하는 식으로,
# 문자열에서 나타나는 모든 110의 경우를 알아낼 수 있습니다.
# 110을 모두 제거한 문자열과, 110의 개수를 우선 얻어보자.
# 스택으로 해결하면 됩니다.
answer = []
for arr in s:
stack, num110, i = [], 0, 0
while i < len(arr):
if arr[i] == '0':
if len(stack) >= 2 and stack[-2] == '1' and stack[-1] == '1':
stack.pop()
stack.pop()
num110 += 1
i += 1
else:
stack.append(arr[i])
i += 1
else:
stack.append(arr[i])
i += 1
# 뒤에서부터 읽어가면서, 처음 나타나는 0 뒤에 110들을 다 붙여줍니다.
# 우선 stack을 뒤집고 0을 찾으면 뒤에서부터 몇 번째(0-based)에 0이 처음으로 나오는지 셉니다.
stack = ''.join(stack[::-1])
idx = stack.find('0')
if idx != -1:
# 0이 있으면 뒤에 붙입니다.
res = stack[:idx] + '011' * num110 + stack[idx:]
else:
# 0이 없으면 그냥 맨 앞에 붙입니다.
res = stack + '011' * num110
answer.append(''.join(res[::-1]))
return answer
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges