문제 해결
1. 스택을 활용한 문제. S3
2. '(' 가 나오면 막대기의 시작점이라 생각하고 stack 에 쌓는다.
3. ')' 이 나왔을 때 두가지의 경우
(1) 이전에 '(' 가 나온 경우: 쇠막대기가 아니라 레이저 이므로 잘라준다.
(2) 이전에 ')' 가 나온 경우: 쇠막대기의 끝 부분 이다.
4. 레이저로 자른경우는 stack 에 쌓여있는 막대기만큼 count를 더해준다.
5. 쇠막대기의 끝부분이 나온경우 막대히 하나만큼 count를 더해준다.
🚗
소스 코드
bars = input()
stack = []
cnt = 0
# '('를 막대기의 시작점으로 주고 '()' 이렇게 여는괄호와 닫는괄호가 연속으로 나오면 레이저로 취급한다.
for i in range(len(bars)):
if bars[i] == '(': # 현재 왼쪽 괄호이면 스택에 쌓고
stack.append(bars[i])
else: # 현재 오른쪽 괄호일 경우
if bars[i-1] == '(': # 이전에 왼쪽 괄호 일 때 : () 이렇게 되면 레이저 이므로
stack.pop() # 막대기의 시작점일거라 예상했던 '('를 하나 빼주고
cnt += len(stack) # 막대기가 담겨있는 stack 의 길이만큼 더해준다.
elif bars[i-1] == ')': # 이전에 오른쪽 괄호 일 때:
stack.pop() # 막대기의 끝부분이므로 '('를 하나 빼주고
cnt += 1 # 막대기 하나가 끝났으므로 1을 더해준다.
print(cnt)
출처 : BACKJOON ONLINE JUDGE
문제 : https://www.acmicpc.net/problem/10799
문제여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.
아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.
이러한 레이저와 쇠막대기의 배치는 다음과 같이 괄호를 이용하여 왼쪽부터 순서대로 표현할 수 있다.
위 예의 괄호 표현은 그림 위에 주어져 있다. 쇠막대기는 레이저에 의해 몇 개의 조각으로 잘려지는데, 위 예에서 가장 위에 있는 두 개의 쇠막대기는 각각 3개와 2개의 조각으로 잘려지고, 이와 같은 방식으로 주어진 쇠막대기들은 총 17개의 조각으로 잘려진다. 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 주어졌을 때, 잘려진 쇠막대기 조각의 총 개수를 구하는 프로그램을 작성하시오. 입력한 줄에 쇠막대기와 레이저의 배치를 나타내는 괄호 표현이 공백없이 주어진다. 괄호 문자의 개수는 최대 100,000이다. 출력잘려진 조각의 총 개수를 나타내는 정수를 한 줄에 출력한다. |
'Algorithm Problem > Python' 카테고리의 다른 글
[python] SWEA - 1961. 숫자 배열 회전/ 1970. 쉬운 거스름돈/ 10059. 유효기간 (0) | 2020.07.14 |
---|---|
[python] SWEA - 1946. 간단한 압축 풀기/ 1945. 간단한 소인수분해 (0) | 2020.07.13 |
[python] 백준 - 2941. 크로아티아 알파벳 (0) | 2020.07.05 |
[python] 백준 - 11399. ATM (0) | 2020.07.03 |
[python] 백준 - 11047. 동전 0 (0) | 2020.07.02 |