둔필승총

https://www.acmicpc.net/problem/10799

[나의 문제 분석]

문제가 복잡하게 적혀 있는데 괄호로 표현해주어서 이해하기 쉬웠다. 처음에 생각한것은 쇠막대기와 레이저의 출발과 끝을 따로 배열로 저장해서 하나씩 볼려고 하였다. 물론 직관적으로 바로 풀었는데 O(n^2)이라서 문제 맞추면 더 좋은 풀이 생각해야지 했더니만 역시.. 시간초과가 뜨고 말았다.

[처음 풀이] 예시들은 제대로 출력되지만 더 빠른 방법이 정답일것 같았다.

s=input()
pipe=[]
raser=[]
stack=[]
answer=0
for i in range(len(s)):
    if s[i]=='(':
        stack.append(i)
    elif s[i]==')':
        if s[i-1]=='(':
            stack.pop()
            raser.append((i-1,i))
        else:
            pipe.append((stack.pop(),i))
for i in pipe:
    count=0
    for j in raser:
        if i[0]<j[0] and i[1]>j[0]:
            count+=1
    answer+=count+1
print(answer)

괄호는 '(', ')' 두개밖에 없고 '('인 경우는 쇠파이프 1개가 새로 시작하거나, 레이저인 경우밖에 없고, ')'인 경우는 쇠파이프 1개가 끝나거나 레이저인 경우밖에 없으므로 결국 input받은걸 하나씩 분석해가면 O(n)안에 문제를 해결할 수 있다.

[나의 해결 방안]

'('인 경우에는 stack안에 집어넣고 ')'인 경우 앞에 것이 바로 '('이면 레이저이므로 stack에 넣은 '('를 빼내준다. 그리고 레이저로 자르면 되는데 이때는 stack의 크기만큼 나온다.

그리고 ')'를 만났는데 그 앞에게 ')'인 경우는 막대기 하나가 끝난경우로 보면 되므로 stack에서 하나 pop해주고 정답을 +1해준다.

s=input()
stack=[]
answer=0
# '('가 들어오는 경우 -> 쇠파이프 1개가 새로 시작하거나, 레이저인 경우
# ')'가 들어오는 경우 -> 쇠파이프 1개가 끝나거나, 레이저인 경우
for i in range(len(s)):
    if s[i]=='(':
        stack.append(i)
    elif s[i]==')':
        if s[i-1]=='(':
            stack.pop()
            answer+=len(stack)
        elif s[i-1]==')':
            stack.pop()
            answer+=1
print(answer)

[다른 사람 풀이]

거의 비슷한것 같다.