프로그래머스 길찾기 문제

접근 방식(알고리즘 분류)

• 스택 + 큐

내 풀이

from collections import deque

def solution(s):
    answer = []
    for string in s :
        stack = []
        count = 0
        for s in string:
            # 문자열이 0이면
            if s == '0':

                # 앞에 2개가 1, 1인지 확인
                if stack[-2:] == ['1', '1']:
                    count += 1
                    stack.pop()
                    stack.pop()

                # 앞에 2개가 1, 1이 아니면 그냥 0을 추가
                else:
                    stack.append(s)

            # 문자열이 0이 아니면 그냥 추가
            else:
                stack.append(s)

        # 110이 없기 때문에 변화 불가능
        print(count)
        if count == 0:
            answer.append(string)

        # 110이 있다면
        else:
            final = deque()

            # 0이 나오기 전까지는 append
            while stack:
                if stack[-1] == '1':
                    final.append(stack.pop())
                elif stack[-1] == '0':
                    break

            # 0이 나왔다면 110을 주어진 count만큼 append
            while count > 0:
                final.appendleft('0')
                final.appendleft('1')
                final.appendleft('1')
                count -= 1

            # stack에 남아있는거 다 추가
            while stack:
                final.appendleft(stack.pop())
            answer.append(''.join(final))
    print(answer)
    return answer

solution(["1110","100111100","0111111010"])

풀이 설명

• 처음에는 python 특성을 이용해서 slice로 접근했다.
• 하지만 결국 해결하지 못하고 답을 참고했다.
• 풀이 설명은 주석을 통해서 적어두었다.

느낀점

• 스택, 큐 와 같은 자료구조를 사용할 생각을 잘 못하는 것 같다.
• 앞으로는 자료구조로 풀 수 있는지 여부를 먼저 생각해야겠다.
• 이 문제는 다음에 한번더 풀어볼 가치가 있는 문제이다.