괄호의 배열에서 쇠막대기 개수 찾기

algorithm | May 14, 2020

()(((()())(())()))(())
이러한 배열에서 () 모양이 생기는 부분은 쇠막대기를 자르는 레이저 위치이다.
쇠막대기들은 위아래로 쌓여있고, 쇠막대기 간의 끝부분은 겹치지 않는다.
레이저에 의해 잘리는 쇠막대기의 총 개수를 구하라.

프로그래머스에서 level 2 라고 하는데… 어떻게 접근해야할지 너무나 막막했던 문제.
괄호 하나하나 온갖 케이스를 if 문으로 체크하면서 삽질하다가 힌트를 얻었다.
괄호의 배열에만 집중하고 있었는데, 잘린 쇠막대기가 어떻게 생겨나는지 그것부터 이해를 하는 게 중요했다.

stack 을 활용해서 괄호의 모양에 따라 list에 넣고 pop하는 방식으로 풀어야 한다고 생각했다.
그런데 그렇게 하려면, if문이 이중으로 들어가야 할 것 같았다.
이때 replace 를 활용해서 레이저의 위치만 알게 된다면, ’(’ 다음에 ’)‘가 온다는 걸 따로 체크를 하지 않아도 된다.

문제의 이해

’()‘를 ‘0’ 으로 replace 해보면 괄호의 배열은 다음과 같다.

0(((00)(0)0))(0)

1. (일 경우에는 쇠막대기가 하나씩 생겨난다.

• 쌓인 쇠막대기 수 += 1
• 잘린 쇠막대기 수 변화없음
  (막대기가 쌓이기만 했고 잘리지는 않았으므로 잘린 쇠막대기의 수는 늘어나지 않는다.)

2. )일 경우에는 쇠막대기가 하나씩 사라진다.

• 쌓인 쇠막대기 수 -= 1
• 잘린 쇠막대기 수 += 1
  (쇠막대기가 끊겼으므로 끊긴 시점에 무조건 쇠막대기 파편이 하나 생기게 되므로 잘린 쇠막대기 수가 늘어난다.)

3. 0일 경우에는 현재 쌓여있는 쇠막대기들이 무조건 잘린다.

• 쌓인 쇠막대기 수 변화없음
  (쇠막대기가 새로 쌓인 게 아니라 기존의 쇠막대기들을 레이저가 자르는 과정만 있다.)
• 잘린 쇠막대기 수 += 현재 쌓인 쇠막대기 수
  (현재 쌓인 쇠막대기들을 레이저로 자르면 그 수만큼 파편이 생겨나기 때문에 그 수만큼 늘어난다.)

Model Solution

def solution(arrangement):
    arrangement =  arrangement.replace('()', '0')
    bars = 0
    answer = 0

    for i in arrangement:
        if i == '0':
            answer += bars
        elif i == '(':
            bars += 1
        else:
            bars -= 1
            answer += 1

    return answer

• 문제를 먼저 이해하는 게 가장 중요하다는 것을 깨달았다.
  어떤 원리로 접근을 해야하고 단계별로 어떤 현상이 벌어지는지를 먼저 확실히 이해하고,
  그 다음에 그걸 코드로 구현하는 것이 삽질을 줄일 수 있는 방법인 것 같다!

Reference: 프로그래머스 스택/큐 쇠막대기 문제