BOJ #10799 쇠막대기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

문제 10799. 쇠막대기

문제 풀이

일반적으로 "stack" 자료구조 개념만 들어간 문제는 고난도 문제가 그리 많지 않지만 이 문제의 경우 재귀나 다른 알고리즘 개념이 들어있지 않아 난이도가 낮은 실버3으로 책정되었음에도 stack 활용에 있어 문제내용의 이해를 요구해 체감 난이도는 한두 단계 위로 책정해도 될만한 문제라 생각한다.

'('과 ')'이 서로 인접할 경우 레이저로 판단하고 떨어져 있는 경우 쇠막대로 간주한다는 점을 유의해야 한다. 그렇다면 '('의 좌표값은 항상 stack에 보관하고 ')'의 좌표값에 대해 연산을 해주면 될 것이다.

• stack 가장 위에 저장된 좌표값이 ')'의 좌표값과 차이가 1일 때

  레이저라는 뜻으로 우선 pop하여 제거한 뒤 남아있는 stack들은 쇠막대를 의미하므로 stack 길이 만큼의 쇠막대의 개수가 생성된다.

• stack 가장 위에 저장된 좌표값이 ')'의 좌표값과 차이가 1을 초과할 때

  쇠막대의 끝점을 의미한다. 한 개의 쇠막대에 N만큼의 레이저로 자르면 N + 1개의 조각이 생성된다는 점을 고려할 때, 끝 조각 1을 더해야 한다.

python 코드

from sys import stdin
input = stdin.readline

s = input().strip()
stack = []
sol = 0
for i, char in enumerate(s):
    if not stack: # stack에 아무것도 없으면 삽입 후 skip
        stack.append(i)
        continue
    elif char == ')': # 뒷부분일 경우
        tmp = stack.pop() # 우선 pop
        if i - tmp > 1: # pop된 좌표와 차이가 1보다 크면 쇠막대
            sol += 1 # 마지막 조각 추가
        else: # 1이면 레이저
            sol += len(stack) # stack에 남아있는 쇠막대 개수만큼 추가
        continue # ')'은 넣을 필요 없으므로 skip
    stack.append(i)