[백준] 10799 쇠막대기 - python

https://www.acmicpc.net/problem/10799

10799번: 쇠막대기

 

문제를 읽어보면 '()' 괄호 쌍은 무조건 레이저다. 각 쇠막대기의 끝은 '(' 와 ')'로 나타내며, 쇠막대기 끼리는 겹칠 수 있으나 레이저와 각 쇠막대기의 끝은 겹치지 않는다.

 

처음에는 각 쇠막대기별로 몇개의 레이저를 지나가는지 체크해주는 방향으로 접근했다.

• '(' 하나만 등장하는 경우 stick 배열에 0을 넣는다.
• '(', ')'이 연속해서 등장하는 경우 stick 배열 안의 요소를 +1 해주기.
• ')'이 등장하는 경우 stick 배열에서 pop() 해준다. 

첫번째 시도 코드는 다음과 같다. 사실 작성하면서 stick 배열을 계속 반복하는데 시간초과나는 거 아니야? 싶었다.

import sys

input = sys.stdin.readline

data = input().replace("\n", "")

stick = []
razor = []

answer = 0
i = 0
while i < len(data):
    if data[i] == "(":
        if i != len(data) - 1 and data[i + 1] != ")":
            stick.append(0)
        elif i != len(data) - 1 and data[i + 1] == ")":
            stick = [i + 1 for i in stick]  # 레이저 수 count
            i += 2
            continue
    else:
        answer += stick.pop() + 1  # 레이저 수 + 1 = 조막 수
    i += 1

print(answer)

...^^

슬픈 예감은 틀리지 않지... 한 67%에서 시간초과가 났다. 

 

그래서 접근 방향을 바꿨다. for 반복문을 쓰지 않는 식으로 해주려면 이제 레이저의 관점에서 접근하면 될 것 같았다. 각각의 레이저가 그 순간 몇개의 쇠막대기를 지나가는지 세어주어도 똑같이 풀릴 것 같았다.

• '(' 하나만 등장하는 경우 현재 유효한 cutting_stick 값을 +1 해준다.
• '(', ')'이 연속해서 등장하는 경우 razor 배열 안에 cutting_stick을 append() 해주었다. 즉 razor[0]의 값은 0번째 레이저가 몇개의 쇠막대기를 지나가는지 저장하고 있다.
• ')'이 등장하는 경우 stick 배열에서 pop() 해준다.

최종 답안은 razor 배열 요소의 합과 총 stick의 개수를 더한 값이다. 따라서 쇠막대기가 등장할 때마다 total_stick이라는 이름의 변수로 매번 카운트해줬다.

 

최종 코드는 다음과 같다.

import sys

input = sys.stdin.readline

data = input().replace("\n", "")

cutting_stick = 0
total_stick = 0
razor = []

i = 0
while i < len(data):
    if data[i] == "(":
        # 쇠막대기 등장
        if i != len(data) - 1 and data[i + 1] != ")":
            cutting_stick += 1
            total_stick += 1
        # 레이저 등장
        elif i != len(data) - 1 and data[i + 1] == ")":
            razor.append(cutting_stick) # 몇개의 막대기를 지나가는지 count
            i += 2
            continue
    # 쇠막대기 끝
    else:
        cutting_stick -= 1
    i += 1

print(sum(razor) + total_stick)

제일 짜릿한 화면

 

---

 

모든 문제가 이렇게 아이디어가 바로 잡혔으면 좋겠다. 매일 정진하자!