-
10799. [Python]쇠막대기Python_알고리즘/Silver II 2023. 2. 13. 00:44
1. 문제
https://www.acmicpc.net/problem/10799
10799번: 쇠막대기
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저
www.acmicpc.net
2. 접근 방법
- 시간 제한: 1초
- 메모리 제한: 256MB
- 스택
3. 파이썬 코드
# input 문자열 info = input() # 문자를 담을 리스트 stack = [] # 갯수 체크 cnt = 0 # enumerate 로 index와 value 값을 가져옴 for i,v in enumerate(info): # 여는 괄호일 경우 if v == "(": # 스택에 index 값 추가 stack.append(i) # 레이저인지 막대인지 모르지만 갯수 추가 cnt += 1 # 닫는 괄호가 나왔을 경우 else: # check 라는 변수에 stack의 제일 뒤값을 뽑아본다. check = stack.pop(-1) # 만약 뽑은 값의 +1 과 닫는괄호의 인덱스가 같은경우 => () 인 경우라서 레이저다 if check+1 == i: # cnt로 체크해둔 값을 -1 해준 후 그때까지 저장된 스택의 길이를 더해준다. cnt -= 1 cnt += len(stack) print(cnt)
4. 문제를 풀고난 후 생각
- 문제를 보자마자 enuermate를 사용하여 index, value 두개의 값을 가지고 풀어야 겠다고 생각했다.
- 문자열 input을 그대로 가져와서 반복문을 통해서 값들을 확인해가며 여는괄호 "("일 경우 stack에 index 값을 추가해주고 막대기 갯수를 체크해주는 cnt 변수를 생성한 후 +1 을 해줬다.
- 이후 반복을 진행하다 닫는 괄호가 나왔을 경우 stack 에 제일 끝값을 뽑아서 +1 해준 값과 현재 index 값을 비교한다.
- 비교해서 같은 경우 즉 "()" 레이저인 경우 막대의 갯수를 세어주는 cnt 변수에 다시 -1을 해주고 막대기가 레이저로 반으로 나눠졌기 때문에 stack에 들어있는 길이만큼 더해주면 된다.
5. 문제를 푸는데 도움이 되는 지식
- 스택
- Python enuermate
'Python_알고리즘 > Silver II' 카테고리의 다른 글
1260. [Python]DFS와 BFS (0) 2023.08.08 1874. [Python]스택 수열 (0) 2023.08.07 1541. [Python]잃어버린 괄호 (0) 2023.08.06 1024. [Python]수열의 합 (0) 2023.08.04 1254. [Python]팰린드롬 만들기 (0) 2023.08.04