[프로그래머스] 110 옮기기

문제 요약

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

문자열에서 110을 뽑아 임의의 위치에 삽입하는 과정을 반복한다.

이때 사전순으로 앞에 오도록 만들어야 하고 더 이상 만들 수 없다면 값을 반환한다.

사전순으로 앞에 오도록 하는게 뭘까했는데 더 작은 숫자라고 생각하면 된다.

접근

110을 삽입해 더 작은 숫자를 만들려면 111이 있는 자리에 110을 삽입해야한다.

for문으로 문자열을 첫번째 숫자부터 확인하면서

111과 110을 찾기 위해 가장 처음 1을 만나면 해당 인덱스값을 idx에 저장해준다.

cnt 변수로 연속되는 1의 수를 세어준다.

0을 만나면,

cnt가 1이하일 때는 의미가 없으므로 다시 cnt를 0, idx를 -1로 설정해주고

cnt가 2일 때는 110을 찾았기 때문에 뽑을 인덱스로 저장해줘야한다.

cnt가 3이상일 때는 111을 찾은 것이기 때문에 뽑힐 인덱스로 저장해줘야한다.

이 부분에 대한 코드는 아직 작성하지 못했다.

코드

def solution(s):
    cnt = 0
    idx = -1
    for x in s:
        for i in range(len(x)):
            if x[i] == 1:
                if idx == -1:
                    idx = i
                cnt+=1
            else:
                if cnt<=1:
                    cnt=0
                    idx=-1
                elif cnt==2:
                    x=x[:idx]+[i-2:i+1]+[1,1,1]+[idx]



    return

 

참고 코드

def mv(temp):
    stack = []
    more = ['1', '1', '0']
    cnt = 0
    for i in temp:
    	# 0 이고 stack의 맨뒤가 1 1 이라면 1 1 제거, cnt+=1
        if i == '0' and stack[-2:] == ['1', '1']:
            cnt += 1
            stack.pop()
            stack.pop()
        else: 
            stack.append(i)
    cnt2 = 0
    stack_len = len(stack)
    answer = []
    if cnt != 0:
        for i in stack:
            if i == '1' and cnt2+1 < stack_len and stack[cnt2+1] == '1':
                answer = stack[:cnt2] + cnt*more + stack[cnt2:]
                answer = "".join(answer)
                break
            cnt2 += 1
        if not answer:
            if '0' in stack:
                cnt3 = 0
                for i in stack[::-1]:
                    if i == '0':
                        answer = stack[:stack_len-cnt3] + \
                            cnt*more + stack[stack_len-cnt3:]
                        answer = "".join(answer)
                        break
                    cnt3 += 1
            else:
                answer = cnt*more+stack
                answer = "".join(answer)
        return answer
    else:
        return temp


def solution(s):
    answer = [mv(i) for i in s]
    return answer

 

출처 https://velog.io/@denhur62/110-%EC%98%AE%EA%B8%B0%EA%B8%B0