LV3 110옮기기 (Python)

 

---

 

문제

 

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

프로그래머스

 

풀이

해당 문제는 "110" 을 찾아서, 어떻게 옮길지가 관건인 문제다.

 

우선 "사전순으로 앞서는" 숫자의 개념을 생각해보자.

 

10과 01이 있을경우 사전순으로 앞서는 숫자는 01이다.

10은 10진수로 2이고, 01은 1이다.

 

이 말은 2진수로 나타낸 숫자를 10진수로 바꾸었을때, 작은 숫자가 사전순으로 앞선다는 뜻이다.

동시에 2진수는 왼쪽일수록 가중치가 높아지기 때문에 작은 숫자를 만들기 위해서는 최대한 높은 가중치에는 1이 아니라 0이 존재해야 한다.

 

110은 0이 하나 존재하기 때문에, 1로만 이루어진 비트 앞쪽에 위치해야한다.

 

예로 10101011 과 같은 숫자에 110을 어디에 넣어야할지 고민해보면, 마지막 0 뒤에 넣어야 한다.

마지막 0이라는 건 무엇을 의미하나? 이제 그 뒤로는 1만 존재한다는 뜻이다.

 

우리는 0을 포함하고 있는 110을 넣을 위치를 찾고 있고, 위에서 말한대로 최대한 0을 높은 가중치에 넣어야 한다. 이 말은 1을 최대한 뒤로 보내야 한다는 뜻이다. 그러므로 0을 하나라도 포함하는 110이라는 값을 "마지막 0" 뒤에 넣음으로써 0을 높은 가중치에 둠과 동시에 1을 낮은 가중치에 두는것이다.

 

...

 

따라서 문자열에서 110을 모두 없애면서 110의 개수를 체크한다. 그리고 110이 들어갈 위치를 찾고 삽입해주면 된다. 110을 모두 제거한 후의 문자열에 0이 존재한다면 마지막 0 이후에 110을 넣어주면 되고, 0이 없다면 110을 문자열 가장 앞에 넣어주면 된다.

 

단 문자열을 제거하는 경우에는 스택을 활용하여 시간초과를 피해야한다. 이또한 중요한 포인트이다.

 

코드

def solution(ss):
    answer = []
    for s in ss:
        cnt = 0
        
        st = [] # stack
        for val in s:
            # 스택에서 110을 발견한다면
            if len(st) >= 2 and val == "0" and st[-1] == "1" and st[-2] == "1":
                cnt +=1
                st.pop()
                st.pop()
            else:
                st.append(val)
        
        # 뒤부터 돌면서 0이 존재하는지 검사한다.
        zero_idx = -1
        
        for i in range(len(st)):
            if st[i] == "0":
                zero_idx = i
        
        # 0이 없다면 -> 110을 앞에 붙여준다.
        if zero_idx == -1:
            answer.append("110" * cnt + "".join(st))
                          
        # 0이 있다면, 그 중간에 붙여준다.
        else:
            answer.append("".join(st[:zero_idx+1]) + "110" * cnt + "".join(st[zero_idx+1:]))
                
    return answer

 

후기

 

난 아래의 두 블로그를 참고하고 풀이했다.

 

전혀 접근하지 못했는데 풀이 방식을 잘 이해할 수 있었고, 특정 문자를 제거할때 스택을 활용해야 한다는 꿀팁도 얻어갔다. 난 구현 문제 보다는 이런 아이디어를 생각해야하는 문제에 약한 거 같다. 따라서 요새는 난이도에 구애 받지 않고 다양한 문제를 풀어봐야겠다고 생각중에 있다..

 

 

 

https://yabmoons.tistory.com/668

[ 프로그래머스 [ 월간코드챌린지 ] 110 옮기기 ] (C++)

 

https://studyandwrite.tistory.com/337

[프로그래머스 / 파이썬(Python)] 110 옮기기