백준 10799번 - 쇠막대기 [python]

Python 코드

s = input() # 괄호가포함된 문자열 입력 받기

stack = [] # 스택 초기화
cnt = 0 # 쇠막대기 조각 개수 초기화

for i in range(len(s)):
    if s[i] == '(': # 열린 괄호의 경우 스택에 push
        stack.append(s[i])
    else: # 닫힌 괄호인 경우
        stack.pop() # 스택에서 pop
        if s[i-1] == '(': # 직전이 열린 괄호였을 경우, (레이저인 경우)
            cnt += len(stack) # 쇠막대기 조각 개수 추가
        else: # 직전이 닫힌 괄호 였을 경우, (쇠막대기 끝인 경우)
            cnt += 1 # 쇠막대기 조각 개수 추가
print(cnt) # 쇠막대기 조각 개수 촐력

Python 코드 풀이

이번 문제는 레이저로 쇠막대기를 자르는 과정에서 생기는 쇠막대기 조각의 개수를 구하는 문제입니다.

문제에서는 5개의 쇠막대기를 사용했으며, 각 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓을 수 있다고 명시되어 있습니다. (끝점은 겹치지 않는다는 조건이 추가되어 있습니다)

레이저는 '()'으로 표현되며, 쇠막대기의 왼쪽 끝은 '('로, 오른쪽 끝은 ')'로 표현됩니다.

이 문제는 스택 자료구조를 이용하여 해결했습니다. 열린 괄호 '('는 스택에 push하고, 닫힌 괄호 ')'는 스택에서 pop합니다.

여기서 중요한 부분은, 직전에 열린 괄호 '('이었을 경우 해당 위치는 레이저를 의미합니다. 따라서, 이때는 스택에 남아있는 쇠막대기의 개수만큼 쇠막대기 조각의 개수를 더하게 됩니다. 반대로, 직전에 닫힌 괄호 ')'이었을 경우 해당 위치는 쇠막대기의 끝을 의미하므로, 쇠막대기 조각의 개수를 1개 더하게 됩니다.

마지막으로, 계산된 쇠막대기 조각의 개수를 출력하면 됩니다.

더 궁금한 점이 있으시다면 언제든지 질문해주세요!