[Baekjoon] 10799번: 쇠막대기(스택 Silver2) - Python

1. 문제

쇠막대기

2. 풀이

2.1 시간초과

my_string = input()

laser_positions = []
bar_positions = []

stack = []

for i, char in enumerate(my_string):
    if char == "(":
        stack.append(i)
    elif char == ")" and stack:
        start = stack.pop()
        if i - start == 1:
            laser_positions.add(start)
        else:
            bar_positions.append((start, i))

total_count = 0

for start, end in bar_positions: // [(4, 9), (10, 13), (3, 16), (2, 17), (18, 21)]
    count = 1
    for pos in laser_positions: // [0, 5, 7, 11, 14, 19]
        if start < pos < end:
            count += 1
    total_count += count

print(total_count)

1. 쇠막대기의 시작과 끝의 위치를 bar_positions 리스트에 저장하고 레이저의 위치를 laser_positions 리스트에 저장한다.
2. 쇠막대기의 위치 값을 순차적으로 조회하면서, 쇠막대기가 위치한 범위 내에서 레이저가 존재할 경우에 카운트 값을 증가시켜준다.
3. 괄호 문자의 개수는 최대 100,000이므로 최악의 경우 시간 복잡도는 O(10^10)이다.

2.2 풀이성공

my_string = input()
stack = []

count = 0

for i, char in enumerate(my_string):
    if char == "(":
        stack.append(i)
    elif char == ")" and stack:
        start = stack.pop()
        if i - start == 1:
            count += len(stack) 
        else:
            count += 1

print(count)

3. 로직

1. 쇠막대기와 레이저의 배치를 나타내는 괄호 표현을 입력받는다.
2. 반복문을 사용하여 문자열을 한 글자씩 순회하면서 괄호의 열림과 닫힘을 처리한다.
3. 여는 괄호 '('를 만나면 스택에 해당 위치를 저장한다.
4. 닫는 괄호 ')'를 만나고 스택이 비어있지 않다면, 스택에서 가장 최근에 저장된 위치를 꺼내고, 이전 여는 괄호와의 거리를 확인한다.

• 거리가 1이라면, 레이저임을 의미하므로, 현재 스택에 쌓인 쇠막대기의 개수만큼 조각을 추가한다.
• 거리가 1이 아니라면, 새로운 쇠막대기의 끝을 의미하므로, 조각을 하나 추가한다.

5. 계산된 조각의 총 개수를 출력한다.