[ 프로그래머스 ] 110 옮기기 파이썬python 풀이

 

// 문제요약

 

0과 1로 이루어진 문자열이 하나 이상 주어지면

 

각 문자열의 부분 문자열 중 110에 해당하는 부분을 추출하여

 

위치를 바꾸는 과정을 거친다고 할때

 

사전 순서에서 가장 앞서는 문자열들을 찾아 반환하여라

 

 

// 사고

 

'사전순서'라하면 dfs가 번뜩 떠올랐지만 주어지는 문자열의 길이가 어마어마해서

 

다른 방식으로 접근해야한다고 생각했다.

 

만약 다른 문제에서 '사전순서'를 미리 만나지 못했다면

 

문제를 이해 하는데만 엄청 오래 걸렸을 것이다.

 

그래도 조금씩 성장하는 모양이다.

 

110 의 경우는 이미 사전순서로 배열이 잘 이루어진 문자열이므로

 

0을 만나면 그 0의 뒤에

1을 만나면 그 1의 앞에

 

위치시켜 주면 해결될 일이었다.

 

문제는 111100 이런 문자열의 경우

 

11 [ 110 ] 0 이렇게 추출 후 다시 110이 되므로 주의를 요했는데

 

나는 110을 추출하는 함수를 만들어서 s = extract( s ) 의 방식으로

 

계속 업데이트를 해 주면서 시간 문제가 발생했다.

 

이 부분을 해결할 수 있는 방법은 내가 추출한 지점에서 문자열을 다시 붙여서

 

붙이고 나면 110이 되는지 검사한 후 아니면 지나가는 방법을 써야했는데

 

이미 내 풀이에 생각이 고여서 이걸 생각해내는게 상당히 어려웠다.

 

그리고 사전순서로 앞서는 문자열을 위해서는

 

문자열의 뒤부터 검사하는 것이 훨씬 효율적인데

 

이 거꾸로 인덱스를 세고 range를 사용하는게 익숙하지 않아서 문제가 상당히 발생했다.

 

실전에서는 자신이 없다면 그냥 증가하는 방향으로 뽑아서 음의 부호로 바꿔주는게 낫겠다.

 

코드를 보자.

 

 

// 코드

https://github.com/hyun06000/coding_test_study_with_python/blob/main/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4/level_check/LV3/110_%EC%98%AE%EA%B8%B0%EA%B8%B0.py

hyun06000/coding_test_study_with_python

 

def solution(s):

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

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

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

 

기능별로 두개의 함수를 만들었다.

 

먼저 추출함수는 0을 만나면 앞의 문자열이 11 인지 확인하고

 

맞으면 지워주는 작업을 했는데 이때 속도를 위해서 마지막을 pop하는 스택을 썼다.

 

그리고 지울때마다 횟수를 카운트하여 들어가야하는 110의 수를 함께 리턴했다.

 

그리고 재배치 함수는 빠르게 하기위해 0을 만나면 그 뒤로 붙이고 바로 리턴하였고

 

모두 1로 구성되어 있다면 앞에 붙여주고 리턴하였다.

 

이 두 함수를 순서대로 돌려주면 답을 구할 수 있다.

 

아직 한참 멀었다. 힘내자.