baekjoon - 10799

stk = [] a = list(input()) i = 0 cnt = 0 for i in range(len(a)):     k = i     if a[k] == "(":         stk.append("(")         k += 1         while stk:             if a[k] == "(":                 stk.append(a[k])             else:                 stk.pop()             k += 1         if k - i != 2:             cnt = "".join(a[i:k-1]).count("()") + 1 + cnt                  else:         continue      print(cnt)

처음에 짠 알고리즘은 입력받은 문자열을 stack에 넣어서 ()인 경우 count하지 않고 하나하나 ()을 count하는 방식으로 진행했더니 시간 초과가 떴다. 사실 이 알고리즘을 짜면서도 아 이건 아닌데라고 생각하긴 했지만 이런 방법으로도 구현해보면 좋을 것 같아서 그냥 계속했다.

 

문제를 다시 가만히 들여다보니 아주아주 쉬운! 방법을 알아낼 수 있었다.

일단 첫 번째는 (이면 stack에 append 해주고, )이면 그 앞 문자가 (이라면 -> stack의 len을 count, )이라면 그냥 +1만 해주는 것이다. 

처음 ()의 경우 (를 append해주지만 그다음은 )이고 그럼 pop하기 때문에 stack에 아무것도 없어 0이 더해진다.

그 다음 ((((후 )는 pop후 (((만 남아 3이 더해진다. 그 다음 ()도 3이 더해지고 (()의 경우 4가 더해진다. 그리고 )은 +1, ) +1이 된다. (())도 (()를 하면 stack의 len인 1이 더해지고 그 다음 )은 이전 문자가 )이기 때문에 +1이 된다.

그래서 이 알고리즘을 작성하면

stk = [] a = list(input()) cnt = 0 for i in range(len(a)):     if a[i] == "(":         stk.append("(")     else:         if a[i-1] == "(":             stk.pop()             cnt += len(stk)         else:             stk.pop()             cnt += 1 print(cnt)

이 된다.

 

뭔가 터무니없는 알고리즘을 작성하기보단 문제에 집중해서 쉬운 알고리즘을 찾는데 집중을 해야겠다.