📄 문제
백준
난이도 : Silver 2
문제 제목 : 쇠막대기
✏️ 풀이 1
import sys
str = sys.stdin.readline().strip()
is_laser = True
current_bar = 0
total = 0
stack = []
for v in str:
if v == '(':
stack.append(v)
current_bar += 1
is_laser = True
else:
current_bar -= 1
if is_laser:
total += current_bar
is_laser = False
else:
total += 1
print(total)✅ 풀이 한줄 설명:
스택을 사용하여 규칙을 찾아 쇠막대기 수를 더해준다.
✅ 풀이 자세한 설명:
🍎 규칙 찾기
우선 규칙부터 찾아야 한다.
-
여는 괄호(
()가 나오면 1을 더하고, 닫는 괄호())가 나오면 1을 빼며 각 문자 위치마다 합산 결과를 적어보면 다음과 같다.
-
잘 보면, 레이저를 쏘는 순간(즉,
()이 등장할 때)에 쌓인 막대의 수는()의)위치에 있을 때의 합산 값과 같다.
말이 조금 헷갈릴 수 있는데, 아래 그림의 파란색 숫자가 레이저를 쏘는 순간 쌓인 막대 수와 같은 것을 확인할 수 있다.
-
레이저를 쏘면 쌓인 막대 수만큼의 막대가 새로 생긴다.
-
또한 레이저가 아닌 닫힌 괄호(
)) 등장 시, 한 개의 막대가 새로 생긴다고 볼 수 있다.
-
따라서 총 막대의 수는 다음과 같다.
-
그림이 좀 복잡해서 정리를 해보면 아래처럼 나타낼 수 있다.
따라서 규칙을 정리해보면 다음과 같다.
- 현재 막대 수를 확인하기 위해
(가 나오면+1,)가 나오면-1을 한다. - 레이저(
())가 나오면 총 막대 수에 현재 막대 수를 더해준다. - 레이저가 아닌
)가 나오면 총 막대 수에+1을 해준다.
🍎 필요한 변수 정리
이제 규칙을 찾았으니 코드를 작성해보자!
우선 필요한 변수들을 먼저 정리해보면 다음과 같다.
is_laser:(다음에 바로)가 나오는 것을 확인해야 하기 때문에(== 레이저인지 확인하기 위해),boolean값을 가지는 변수를 둔다.
현재 스택의top에 저장된 값이(이면True, 아니면False다.current_bar: 현재 쌓여있는 막대 수이다.(가 나오면+1,)가 나오면-1해준다.total: 총 막대 수이다.
위의 변수들과 스택을 활용해서 코드를 작성하면 위와 같은 알고리즘 풀이가 나올 것이다.
✏️ 풀이 2
import sys
parentheses = sys.stdin.readline().strip()
stack = []
cutting_count = 0
for ele in parentheses:
if ele == '(':
stack.append(ele)
last = ele
else:
if last == '(':
stack.pop()
cutting_count += len(stack)
last = ele
else:
stack.pop()
cutting_count += 1
print(cutting_count)다른 사람이 푼 풀이인데, '✏️ 풀이 1'과 거의 비슷하지만 is_laser 대신 last 변수를 저장하는 등의 일부 차이점이 존재하여 한 번 적어보았다. 이 풀이에 쓰인 변수명 등이 조금 더 직관적이라고 생각해서 참고하면 좋을 것 같다.
📦 GitHub
해당 문제, 풀이에 대한 GitHub Repository 링크는 다음과 같다.
GitHub - 백준(Silver) '10799. 쇠막대기'
GitHub - [8강] 스택의 활용 (수식의 괄호 쌍)/응용문제 '10799. 쇠막대기'
스택의 활용으로 '수식의 괄호 쌍' 문제의 응용 버전이지만, 단순히 규칙만 잘 찾으면 되는 문제라 생각한다.
➕ 생각해보니 '괄호' 문제이고, 스택을 배운 후에 이 문제를 봐서 스택을 사용했지만, 굳이 스택을 사용하지 않아도 될 것 같다.
'✏️ 풀이 1'의 경우에는 현재 쌓인 쇠막대기의 개수인 current_bar와 총 쇠막대기의 수인 total로 계산을 하고 있어 굳이 스택에 값을 저장할 필요가 없다.
물론 '✏️ 풀이 2'의 경우에는 스택의 길이를 cutting_count에 저장하는 식으로 계산을 하고 있어 스택이 필요하지만, 이 또한 current_bar_count 같은 변수를 두면 스택을 사용하지 않아도 된다.
물론 스택을 사용하는게 굳이 current_bar 변수를 두지 않아도 돼서 더 깔끔할 수 있다. 풀이는 다양하니 그냥 이럴수도 있다는 사실을 알고 넘어가면 좋을 것 같다.
