알고리즘/백준
10799번 쇠막대기 파이썬
글을 쓰는 개발자
2020. 12. 1. 20:31
반응형
문제:www.acmicpc.net/problem/10799
10799번: 쇠막대기
여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저
www.acmicpc.net
처음에 문제를 풀 때 '()'를 'l'로 치환을 한 다음에 두개의 리스트를 만들고 하나의 리스트에는 ')'를 만나기 전까지의 문자를 저장하였고 나머지 리스트는 ')'를 만났을 때 '('를 만나기 전까지의 'l'의 갯수를 센 다음에 저장을 하고 초기화하는 방식으로 풀었다. 그런데 그 결과는 '시간 초과'라는 결과를 가져왔다. 그렇게 된 이유는 최악의 경우에 시간 복잡도가 N^2이기 때문이다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import sys
script = sys.stdin.readline().rstrip()
script = script.replace("()","l")
stk=[]
razer=[]
ret=0
for x in script:
if x=='(':
stk.append('(')
elif x=='l':
if len(stk)!=0:
stk.append('l')
elif x==')':
while stk[-1]!='(':
if len(stk)==0:
break
elif stk[-1]=='l':
razer.append(stk.pop())
if stk[-1]=='(':
stk.pop()
ret+=len(razer)+1
stk+=razer
razer=[]
print(ret)
|
cs |
[Python] 백준 10799 쇠막대기
문제 # 10799 ()를 이용해서 쇠막대기를 만들고, 자르는 문제이다. 예시) 이 경우, 쇠 막대기는 모두 17조각이 난다. 풀이 알고리즘만 알면, 쉽게 해결되는 문제다. 각각 괄호의 의미를 살펴보면, 붙
ilgls1.tistory.com
그래서 풀다가 결국 어떻게 나아가야 할 지 몰라서 검색해서 위의 블로그를 통해 풀이를 참고했다.
')'가 나왔는데 그전의 문자가 '('이냐 또는 ')'인 경우에 따른 경우의 수를 둬서 문제를 해결하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
val = input()
sum=0
left=0
for i in range(len(val)):
if val[i]=='(':
left+=1
elif val[i]==')':
left-=1
if val[i-1]=='(':
sum+=left
else:
sum+=1
print(sum)
|
cs |
반응형