[프로그래머스] 110옮기기 (Python 풀이)

허준현·2021년 8월 31일
0

CodingTest

목록 보기
3/8
post-thumbnail

문제 : https://programmers.co.kr/learn/courses/30/lessons/77886
자세한 문제 구성은 위의 링크를 참조바란다.

Problem Point

x에 있는 "110"을 뽑아서, 임의의 위치에 다시 삽입합니다.
문자열 중 사전 순으로 가장 앞에 오는 문자열을 배열에 담아 return 하도록 solution 함수를 완성해주세요.
간단히 말해서 문자열 안에서 110을 모두 뽑아내고 숫자를 최대한 크게 만드는 방향으로 만드는 것이 포인트 이다.
1 ≤ s의 길이 ≤ 1,000,000

풀이

맨 처음에 접근하였을때는 110을 뽑아내고 나서 그 뒤에 0과 앞에 11이 다시 만나서 뽑아내는 과정을 110을 찾지 못할때까지 반복하여 찾는 방향으로 생각하였다. 하지만 이런 방향은 O(N^2)이며 시간초과가 날 것이라고 생각하였다. 따라서 선형적인 방법으로 접근을 해야 했고 그 중 스택을 사용하여 O(N) 시간에 접근하는 방법을 생각해 냈다.

위의 사진을 보고 잠시 했갈렸다. 숫자를 최대한 크게 만들기 위해서는 11 앞에 110 이 와야 했지만 사진에서는 뒤로 가는 모습을 보여줬기 때문이다. 하지만 자세히 보면 110을 뒤로 옮긴 것이 아닌 11 앞에 보내도 같은 숫자임을 알 수 있다.
여기서 드는 생각이 왜 111이 아니고 11 앞에 와야 하냐고 생각 할수 있는데 11이 나올 수 있는 경우의 수가 110 과 111이기 때문에 적어도 11앞으로 옮기게 되면 숫자가 작아지는 경우는 없다. 따라서 숫자 11앞에 110을 넣는 방향으로 생각하였다.

위 사진은 예시에서 110을 제외한 나머지 숫자들이다. 이제 11이 있는 경우는 해결되었으나 문자 안에 자체가 110이 없는 경우에 대해서 생각해야 했고 list안에 1만 있는 경우에는 맨 앞에 붙이는 것과 0이 있는 경우에는 마지막 0뒤에 붙여야 했다. 따라서 코드를 보면 문자열을 역순으로 돌면서 마지막 0의 index값을 찾아 안에 삽입하는 방식으로 구현하였다.

최종풀이

def mv(temp):
    stack = []
    more = ['1', '1', '0']
    cnt = 0
    for i in temp:
        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
profile
best of best

0개의 댓글