[Python]10799번: 쇠막대기

1차로, regex을 이용한 문제풀이를 해보려 했다.

 

먼저 레이저도 쇠막대기도 모두 괄호로 표현되기때문에, 레이저에 해당하는 ()를 *로 바꿀것이다.

import sys
import re

input = sys.stdin.readline()

input = re.sub(r'(\(\))','*',input)
print(input)

레이저가 잘 대체된 모습

이후에는 regexr을 이용해 괄호를 파악하고, 안에 *이 몇개있는지 세서 piece에 지속적으로 더하도록 코드를 짰다.

이렇게 가장 속 괄호를 파악함

그리고 개수를 파악한 뒤에는 해당 쇠막대가 필요하지 않기 때문에, 해당 요소의 괄호 '('와 ')'을 ' '로 대체했다.

그러니까,

input = '()(((()())(())()))(())'
input = re.sub(r'(\(\))','*',input)
#	*(((**)(*)*))(*) 레이저 처리 이후
ironBarIter = re.finditer(r'\([* ]*\)',input)
# iterator지만 list로 표현하자면 ['(**)', '(*)', '(*)'] 형식으로 저장되어있음

# 이후 반복문에서,
piece+=ironBar.group().count('*')+1	#레이저에 의해 동강나는 개수를 쇠막대마다 추가
input = input[:ironBar.start()]+" "+input[ironBar.start()+1:ironBar.end()-1]+" "+input[ironBar.end():]
# iterator에서 주는 start() end()로 index를 파악해, 괄호만 빼고 새로 문자열을 만든 것.

이런식이다.

문제는... 이런 이중중첩문에서 시간초과가 안일어날리 없다는 것 ㅠ

다른 방법을 모색하기로 했다.

 

 

 

*(((**)(*)*))(*)

 

이걸 골똘히 보다가 떠오른게... 저렇게 문자열 자르고,, 재구성할 필요가 있냐는 생각이 확 들었다.

그냥 string의 char마다 개수 처리를 하는 거임... for문을 한번만 돌테니, O(n)의 시간복잡도가 나올테고?

(가 나오면 쇠막대기수를 +1

*이 나오면 현재 쇠막대기수만큼 잘렸으니까 그걸 piece에 추가

)이 나오면 한 쇠막대기가 끝난거니까 마지막 조각을 고려해서 piece에 +1

 

오마이갓.. 이렇게 쉽게 풀릴 문제를 사람의 관점에서 보느라 완전 복잡하게 풀어내고 있던 것이었다.

import sys
import re

input = sys.stdin.readline()

input = re.sub(r'(\(\))','*',input).rstrip()
#   *(((**)(*)*))(*) 

piece = 0
current_ironBar = 0

for element in input:
    if element == '(':
        current_ironBar +=1
    elif element == '*':
        piece += current_ironBar
    else:   # )
        current_ironBar -= 1
        piece += 1

print(piece)

rstrip을 한건 우측에 띄어쓰기가 되어있는지, 그걸 인식하고 else case로 들어가기에 붙여줬다.

이번에 느낀 건, 문제 파악을 간결하게 할 줄 알아야겠다는 것?

 

여담으로 아랫방법을 쓰면 ()을 *로 바꿔줄 필요도 없겠지?

element '(' 일 경우 flag를 1로 하고, element *대신 element가 ')'이고 flag가 1일때로 바꿔도 될 것임.