백준 10799번: 쇠막대기 (python)

문제

• https://www.acmicpc.net/problem/10799
• 스택을 사용해 반복의 다음 회차 때 필요한 정보만 유지하기

기록 포인트

• for문 대신 while문 사용이 유리한 상황
  • 파이썬에서 배열을 for문으로 탐색하면 배열의 각 아이템을 반드시 체크해주어야 함
  • 반면 while문으로 탐색하면 다음 아이템을 미리 확인하는 등의 절차를 통해 건너뛰기할 수 있음
• 문제에 맞춰 스택에서 관리하는 정보를 정하기
  • 이 문제는 "스택에는 끝나지 않은 막대만 저장한다"로 만들 수 있는 과제였음
    • 시작 괄호라고 해서 무조건 스택에 저장하는 것이 아니라,
    • 시작 괄호가 막대인지 레이저인지 확인해서 막대인 경우에만 스택에 넣음
  • 1차 답안에서는 스택에 레이저까지 저장하도록 구성했고 비효율적인 코드가 늘어났음
    • 물론 다른 문제에서는 이런 상황이 요구될 수도 있지만, 이 문제에서는 더 효율적으로 구성할 방법이 있었음
    • 이 부분은 문제를 잘 분석하는 것이 관건이라고 생각됨

접근 방식

• 제출 답안 참고

제출 답안

최종 답안

• for문 대신 while문 사용
  • 변수 i를 통해 탐색 순서 관리
  • 탐색 중인 배열의 다음 아이템을 미리 확인한 뒤, 필요 시 탐색 순서를 조정
• 하나의 막대가 시작되는 시점에 조각 개수 1 추가
  • 시작 괄호가 등장 시, 레이저 시작을 의미하는지 막대 시작을 의미하는지 구분
  • 막대 시작을 의미할 때, 조각 개수 1 추가

import sys
questions = sys.stdin.readline().rstrip()

stack = []
answer = 0
i = 0
# 레이저의 닫는 괄호를 건너 뛰는 코드를 넣기 위해 for문 대신 while문 사용
while i < len(questions):
    q = questions[i]
    # 시작 괄호인 경우, 레이저인지 막대인지 구분
    if q == "(":
        if questions[i+1] == ")": # 레이저
            answer += len(stack)
            # 다음에 오는 닫는 괄호는 탐색에서 건너 뛰도록 하고
            # 그러므로 레이저 시작 괄호 또한 스택에 넣지 않음
            i += 1 
        else: # 새로운 막대
            answer += 1
            stack.append(q)
    # 닫는 괄호인 경우, 막대를 닫아줌
    else:
        stack.pop()
    i += 1


print(answer)

1차 답안

• for문으로 하나씩 탐색
• 하나의 막대가 끝나는 시점에 조각 개수 1 추가

import sys
questions = sys.stdin.readline().rstrip()

stack = []
answer = 0
sub_count = 0
for q in questions:
    # 시작 괄호인 경우 스택에 추가
    if q == "(":
        sub_count += 1
        stack.append(q)
        continue
    # 끝 괄호인 경우
    # 바로 닫히는 경우, 즉 레이저인 경우
    if stack[-1] == "(":
        # 스택에서 레이저를 뺀 뒤, 남은 시작 괄호의 수를 센다
        stack.pop()
        sub_count -= 1
        answer += sub_count # sum((c == "(" for c in stack))
        # 스택에 L을 추가한다
        stack.append("L")
        continue
    elif stack[-1] == "L":
        # 스택에서 "(" 를 만날 때까지 레이저를 뺀다
        while stack:
            prev = stack.pop()
            if prev == "(":
                # 막대 끝단 개수 추가
                sub_count -= 1
                answer += 1
                # 다시 막대임을 표시
                stack.append("L")
                break

print(answer)