[김태원 알고리즘] 쇠막대기 (스택)

사용 언어: Python3

문제

풀이

내 풀이

strr = input()
stack = [] # 레이저를 표시할 스택

# 레이저를 0으로 표시
for x in strr:
    if x == ')' and stack[-1] == '(':
        stack.pop()
        stack.append('0')
    else:
        stack.append(x)
    
ans = 0
N = len(stack) # stack의 길이는 pop으로 인해 변할 것이기 때문에 미리 저장

# 하나의 괄호쌍()씩 pop 하는 과정 반복
while len(stack) > stack.count('0'): # 모두 pop하고 레이저만 남을 때까지
    isStop = False # 2중 for문 종료 위해
    for i in range(N):
        if stack[i] == ')':
            stack.pop(i)
            tmp = 0 # 그 사이 레이저 수
            for j in range(i-1, -1, -1):
                if stack[j] == '0':
                    tmp += 1
                elif stack[j] == '(':
                    stack.pop(j) # 닫힌 괄호의 짝인 열린 괄호 pop
                    ans += tmp+1 # 사이에 레이저 3개 -> 4조각
                    isStop = True
                    break
            if isStop:
                break

print(ans)

• 먼저 레이저를 0으로 나타내었다.
  • ()(((()())(())()))(()) -> 0(((00)(0)0))(0)
• stack에 0(((00)(0)0))(0)이 담겨있다고 할 때, stack을 순회하며 괄호 쌍들을 pop한다.
  • 이때, 하나의 괄호쌍 사이에 있는 레이저 수를 카운트해서 답(ans)에 누적한다.
  • ex. (00)이라면 괄호쌍 사이에 레이저 2개니까 ans += 3 (쇠막대기는 세 조각나기 때문)
  • 레이저들(000000)만 남을 때까지 괄호쌍을 제거하고 답에 누적하는 과정을 반복한다.

다른 풀이

strr = input()
stack = []

ans = 0
for i in range(len(strr)):
    if strr[i] == '(':
        stack.append(strr[i])
    else: # 닫는 괄호라면
        stack.pop()
        if strr[i-1] == '(': # ✅ 레이저인 경우 (stack[i-1]이 아니라 strr[i-1]이다!)
            ans += len(stack)
        else: # ✅ 쇠막대기가 끝난 경우
            ans += 1

print(ans)

• )일 때, 바로 앞이 (라면 레이저, 바로 앞이 )라면 쇠막대기가 끝난 지점
  • 레이저라면 (을 pop하고 sum += len(stack)
  • 쇠막대기가 끝났다면 (을 pop하고 sum += 1

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기