[백준] #10799. 쇠막대기 (Python)

#10799. 쇠막대기

site: 백준
등급: 실버2
유형: 스택/큐
작성일시: 2023년 7월 7일 오전 2:39

📖Problems

쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오.

레이저와 쇠막대기의 배치: 왼쪽부터 순서대로 표현함

1. 레이저는 ‘( ) ’ 으로 표현함. 모든 ‘( ) ’는 반드시 레이저를 표현
2. 쇠막대기의 왼쪽 끝은 ‘ ( ’ 로, 오른쪽 끝은 ‘) ’ 로 표현

 

예시

 

쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다.

예제1

• 입력: ()(((()())(())()))(())
• 결과: 17

예제2

• 입력: (((()(()()))(())()))(()())
• 결과: 24

🔍Institution

문제 유형 : 스택

• 스택이라고 생각한 이유 : 레이저가 나오기 전까지 ( 를 저장해놔야 하며, 레이저가 나오거나 )표시가 나오면 이전 값들은 필요가 없게 되므로, LIFO 형식의 스택이 적합하다고 판단했다.

예제1 ()(((()())(())()))(())

쉽게 판단하여 아래 코드처럼 아주 간단하게 짰다.

bar = '()(((()())(())()))(())'
stk = []
cnt = 0

for i in bar:
    if i == '(':
        stk.append(i)
    elif i == ')':
        stk.pop()
        cnt += len(stk)
print(cnt)

하지만 예제 2의 입력값을 넣으면 바로 틀리게 된다. 예제2를 보면서 겉규칙이 아닌 근본적인 규칙을 찾아야 한다.

 

예제2 (((()(()()))(())()))(()())

예제 2 과정은 아래 그림과 같다.

 

여기서 example 1처럼 단순히 접근했다면 나처럼 꼬일 수 있다. 규칙을 찾아야 한다. 내가 찾은 규칙은 아래 그림과 같이 이해할 수 있다.

• 빨간색 부분이 레이저 ()를 만났을 때 더해지는 부분이며, 괄호와 같은 색 부분의 네모가 )를 만났을 때 더해지는 부분이다.
• 즉, )가 들어왔을 때에 바로 직전에 (인지 )인지 판단해야 한다.
  • 만약 (라면 stack에 들어있는 ( 의 개수만큼 더해줘야 한다.
  • 반대로 )라면 끄트머리에 있는 1개를 더해주면 된다.

🔍Approach

• 문제유형 : 스택
• 문제 분석
  • ()는 레이저이고, 레이저를 지날 때, 쪼개지게 된다. 위의 그림과 같이 레이저를 지나면 이전 값들이 모두 쪼개져 더해지게 된다.
  • 괄호가 이어져 있지 않는 (와 )는 쇠막대기의 끄트머리를 의미한다.
  • )이 들어왔을 때 바로 앞이 (인지 )인지에 따라 더하는 수가 달라진다. (라면 레이저이므로, stack에 있는 개수만큼 더해준다. )라면 쇠막대기 끄트머리 부분으로 1을 더한다.
• 문제 풀이
  • 입력받는 값은 bar에 저장한다. stack과 총 쇠막대기 조각 개수를 저장할 count 변수인 cnt를 초기화한다.
  • (가 들어오게 되면 stack에 추가한다.
  • 그게 아니라 )가 들어오게 되면,
    • 바로 직전 값이 (라면 (즉, () 레이저를 의미한다. 따라서 쇠막대기가 아닌 레이저이기 때문에 append했던 직전 값인 (를 pop해준다. 이후 남은 값들은 모두 쪼개졌으므로, stack의 길이만큼을 cnt에 더해준다.
    • 바로 직전 값이 )라면, 레이저가 아니다. 직전 값을 함께 pop해주고, 1만큼만 더해준다.
  • 이 과정을 입력받은 값만큼 for문을 반복하며 enumerate를 통해 index를 사용해서 직전 값을 구한다.
  • 이후 최종 cnt값을 출력한다.

🚩My submission

bar = input()       #'(((()(()()))(())()))(()())'
stk = []
cnt = 0

for i, b in enumerate(bar):
    if b == '(':
        stk.append(b)
    elif b == ')':
        if bar[i-1] == '(':     # 만약 ()이라면 
            stk.pop()
            cnt += len(stk)
        else:                   # 만약 ) 앞에 )였다면
            stk.pop()       
            cnt += 1
print(cnt)

삽질 과정

 

1. example 1 풀었을 때는 정말 단순히 풀이했다.

bar = '()(((()())(())()))(())'
stk = []
cnt = 0

for i in bar:
    if i == '(':
        stk.append(i)
    elif i == ')':
        stk.pop()
        cnt += len(stk)
print(cnt)

이러면 example1은 통과한다. 하지만 example 2는 통과하지 않는다.

 

2. example 2를 풀이하기 위한 본격 삽질 과정이 시작된다.

bar = '(((()(()()))(())()))(()())'
stk = []
cnt = 0

for i in bar:
    if i == '()':
        stk.append(i)
    elif i == '(':
        stk.pop()
        cnt += len(stk)
print(cnt)

될리가 없다. 맨 첫 문자가 (로 시작하는데 stack에는 비어있기 때문에 에러가 발생한다.

IndexError: pop from empty list

 

3. 무대뽀로 짠 코드.

bar = '(((()(()()))(())()))(()())'
stk = []
cnt = 0

for i in bar:
    if i == '()':
        cnt += len(stk)
    elif i == '(' or ')':
        stk.append(i)
    elif i == ')':
        stk.pop(i)
print(cnt)

마찬가지로 될리가 없다. 결과는 0이다. 왜냐하면 인덱스는 한 문자씩 인지하기 때문에 ()가 조건문에 걸릴 수가 없다. 따라서 카운트가 아예 되지 않기 대문에 0이 출력된다.

 

4. 거의 다 왔을 때! 머리로, 그리고 직접 더할 때는 당연히 이해하고 넘어가는 부분들을 코드로 했을 때는 다른 결과가 나와 당황했던 부분.

bar = '(((()(()()))(())()))(()())'
stk = []
cnt = 0

for i, b in enumerate(bar):
    if b == '(':
        stk.append(b)
    elif b == ')':
        if bar[i-1] == '(':
            cnt += len(stk)
        else:
            stk.pop()
            cnt += len(stk)

print(cnt)

5. 최종결과!!

bar = input()       #'(((()(()()))(())()))(()())'
stk = []
cnt = 0

for i, b in enumerate(bar):
    if b == '(':
        stk.append(b)
    elif b == ')':
        if bar[i-1] == '(':     # 만약 ()이라면 
            stk.pop()
            cnt += len(stk)
        else:                   # 만약 ) 앞에 )였다면
            stk.pop()       
            cnt += 1
print(cnt)

 

6. 결과

bar = '(((()(()()))(())()))(()())'
stk = []
cnt = 0

for i, b in enumerate(bar):
    print(i+1)
    if b == '(':
        stk.append(b)
        print(stk)
    elif b == ')':
        print(b)
        if bar[i-1] == '(':     # 만약 ()이라면 
            stk.pop()
            cnt += len(stk)
            print(cnt, stk)
        else:                   # 만약 ) 앞에 )였다면
            stk.pop()       
            cnt += 1
            print(cnt, stk)
    print("\n")
print(cnt)

위 코드를 출력하면 아래와 같다. 자신이 한 과정과 맞게 나오는지 비교해보면 좋을 것 같다.

1
['(']

2
['(', '(']

3
['(', '(', '(']

4
['(', '(', '(', '(']

5
)
3 ['(', '(', '(']

6
['(', '(', '(', '(']

7
['(', '(', '(', '(', '(']

8
)
7 ['(', '(', '(', '(']

9
['(', '(', '(', '(', '(']

10
)
11 ['(', '(', '(', '(']

11
)
12 ['(', '(', '(']

12
)
13 ['(', '(']

13
['(', '(', '(']

14
['(', '(', '(', '(']

15
)
16 ['(', '(', '(']

16
)
17 ['(', '(']

17
['(', '(', '(']

18
)
19 ['(', '(']

19
)
20 ['(']

20
)
21 []

21
['(']

22
['(', '(']

23
)
22 ['(']

24
['(', '(']

25
)
23 ['(']

26
)
24 []

24

🚩Others submission

대체로 다 비슷했다.

https://inuplace.tistory.com/844

bar_razor = list(input())
answer = 0
st = []

for i in range(len(bar_razor)):
    if bar_razor[i] == '(':
        st.append('(')

    else:
        if bar_razor[i-1] == '(': 
            st.pop()
            answer += len(st)

        else:
            st.pop() 
            answer += 1 

print(answer)

💡TIL

• 문제를 이해하는데 시간을 많이 썼던 문제이다. 문제 해결도 중요하지만 이렇게 복잡한 문제가 나와도 이해하는 능력을 길러야겠다.
• 왜 이 값이 나오지 않는가, 하여 ppt로 하나하나 만들어서 한 게 도움이 되었다. 실전에서 봤으면 엄청 꼬였을 것 같은 문제이다. 최대한 규칙을 찾아보려고 노력해보자.