프로그래머스 - 스택/큐 - 쇠막대기

02 Mar 2020

문제

입력

---

나의 처음 코드

문제와 같은 비슷한 문제들을 접해본 적이 있을 것이다. 나는 ‘프로그래밍 언어’라는 수업을 들으면서, Parsing 관련 코딩을 할 때 토나올 때까지 접해본 기억이 있다.
이 문제는 스택과 관계가 있다. 스택을 책으로 공부해본 사람이라면, 예제로도 비슷한 예시를 드는 것을 기억할 것이다. 여기에서는 문법오류를 찾는 대신에, ()를 만나면 잘리는 나무막대기의 갯수를 찾는 것이다. 다음과 같은 규칙을 볼 수 있다.

1. ( 의 갯수대로 ()를 만났을 때 왼쪽에 막대기가 생긴다
2. 를 만나면 막대기 갯수 + 1 해준다.
3. 위의 과정 반복
   ) 를 만났을 때, 잘릴 때 추가되는 막대기가 줄어든 다는 것을 생각하면 된다. 규칙을 읽고 이해가 안 간다면 노트에 그림을 그려서 이해하기를 추천한다. 코드는 다음과 같다.

def solution(arrangement):
    #잘리면 추가되는 총 막대기 수
    num_of_bar = 0
    #잘리면 생기는 막대기 수
    cnt_of_left = 0
    arr_idx = 0
    while arr_idx != len(arrangement):
        if arrangement[arr_idx] == '(':
            if arrangement[arr_idx + 1] == ')':
                num_of_bar += cnt_of_left
                arr_idx += 2
            else:
                cnt_of_left += 1
                arr_idx += 1
        else:
            num_of_bar += 1
            cnt_of_left -= 1
            arr_idx += 1

    return num_of_bar

스택이라는 자료구조와 규칙을 찾아서 푸는 문제이다. 자세히 들여다 보면 어렵지 않은데, 그림만 보고 겁을 먹으면 안된다. 그림을 주었다는 것은 설명에 도움이 더 되라는 것이기 때문이다. 호호