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

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

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

문제설명

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

 

입출력 예

 

입출력 예 설명

입출력 예 #1

• 다음 그림은 "1110"을 "1101"로 만드는 과정을 나타낸 것입니다.

• "1101"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "1101"을 담아야 합니다.
• 다음 그림은 "100111100"을 "100110110"으로 만드는 과정을 나타낸 것입니다.

• "100110110"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "100110110"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "100110110"을 만들 수 있습니다.
• 다음 그림은 "0111111010"을 "0110110111"로 만드는 과정을 나타낸 것입니다.

• "0110110111"보다 사전 순으로 더 앞에 오는 문자열을 만들 수 없으므로, 배열에 "0110110111"을 담아야 합니다.
• 그림에 나온 방식 말고도 다른 방법으로 "0110110111"을 만들 수 있습니다.

 

풀이

def solution(s):
    answer = []
    for i in s :
        temp = list(i)
        one_count = 0
        one_index = 0
        index = 0
        while index < len(temp):
            if temp[index] == '1':
                if one_count == 3 :
                    index += 1
                    continue
                else:
                    one_count += 1
                    one_index = index
            elif temp[index] == '0':
                if one_count == 3 :
                    temp[index] = '1'
                    temp[one_index] = '0'
                    one_index, index = index, one_index
                one_count = 0
            index += 1
        answer.append(''.join(map(str,temp)))
    return answer

앞에서부터 연속되는 1을 찾아서 3번째 1이 나온 idx를 저장했다가 뒤에서 110이 나오는 순간 0과 1의 위치를 바꾸는 방식으로 구현을 했다. 테스트 케이스에서는 통과했지만 실제 채점에서는 틀렸다고 나왔는데 어느 부분이 틀렸는지 찾지 못하여서 해답을 보고 구현하였다.

https://prgms.tistory.com/57?category=882795 

[월간 코드 챌린지 시즌 2] 5월 문제 해설

110 해설

stack = []
        count = 0
        for char in string:
            if char == '0':
                if stack[-2:] == ['1','1']:
                    count += 1
                    stack.pop()
                    stack.pop()
                else :
                    stack.append(char)
            else :
                stack.append(char)

stack을 이용하여 string에 있는 모든 110을 뽑아내고 갯수를 세아렸다.

if count == 0 :
            answer.append(string)
        else :
            temp = deque()
            while stack:
                if stack[-1] == '1':
                    temp.append(stack.pop())
                elif stack[-1] == '0':
                    break

110이 하나도 없는 경우에는 string과 답이 동일하기 때문에 answer에 바로 string을 넣었다.
110이 있는 경우에는 끝에서부터 1이 연속되는 동안은 idx를 증가시킨다. 

while count > 0 :
                temp.appendleft('0')
                temp.appendleft('1')
                temp.appendleft('1')
                count -= 1
            while stack :
                temp.appendleft(stack.pop())
            answer.append(''.join(map(str,temp)))

0이 나오는 순간 멈추고 count의 갯수만큼 110을 넣은 뒤 나머지 stack의 내용을 다 넣으면 된다. 110은 0이 포함된 경우의 수 중에서 가장 뒤에 오는 경우이기 때문에 모든 0이 포함된 숫자는 110보다 앞에 와야한다.

 

전체 코드

from collections import deque
def solution(s):
    answer = []
    for string in s :
        stack = []
        count = 0
        for char in string:
            if char == '0':
                if stack[-2:] == ['1','1']:
                    count += 1
                    stack.pop()
                    stack.pop()
                else :
                    stack.append(char)
            else :
                stack.append(char)
        
        if count == 0 :
            answer.append(string)
        else :
            temp = deque()
            while stack:
                if stack[-1] == '1':
                    temp.append(stack.pop())
                elif stack[-1] == '0':
                    break
            
            while count > 0 :
                temp.appendleft('0')
                temp.appendleft('1')
                temp.appendleft('1')
                count -= 1
            while stack :
                temp.appendleft(stack.pop())
            answer.append(''.join(map(str,temp)))
                
    
    return answer

문자열을 비교하기 위해서 리스트로 변환한 뒤 join을 이용하여 다시 합쳤지만 그냥 문자열에서 idx를 이용하여 확인하면서 비교하는 것이 더 효율적일 것 같다.