괄호 문자열 이어 붙이기

시간 제한2초메모리 제한128 MB

요약

괄호 문자열들을 이어 붙일 순서를 정해 올바른 괄호 문자열을 만들 수 있는지 판정합니다.

난이도: 보통10점 중 6점
유형: 그리디, 정렬, 누적 합
정답자: 아직 제출이 없습니다

문제

(와 )로만 이루어진 문자열 $n$ 개 $str_1, str_2, \ldots, str_n$ 이 주어진다. 이 $n$ 개의 문자열을 어떤 순서로 나열해 모두 이어 붙였을 때 올바른 괄호 문자열이 되게 만들 수 있는지 판별하라. 문자열의 순서만 바꿀 수 있고, 각 문자열 내부는 그대로 둔다.

올바른 괄호 문자열은 다음과 같이 정의한다.

빈 문자열은 올바른 괄호 문자열이다.
$A$ 와 $B$ 가 올바른 괄호 문자열이면 $A$ 와 $B$ 를 이어 붙인 문자열도 올바른 괄호 문자열이다.
$A$ 가 올바른 괄호 문자열이면 $A$ 를 괄호 한 쌍으로 감싼 문자열도 올바른 괄호 문자열이다.
그 밖의 문자열은 올바른 괄호 문자열이 아니다.

예를 들어 ()()와 (())는 올바른 괄호 문자열이고, ())와 ((()는 올바른 괄호 문자열이 아니다.

입력

첫째 줄에 문자열의 개수 $n$ ( $1 \le n \le 100$ )이 주어진다. 이어지는 $n$ 개의 줄에 문자열 $str_i$ ( $1 \le |str_i| \le 100$ )가 한 줄에 하나씩 주어진다. $str_i$ 의 모든 문자는 ( 또는 )이다.

출력

올바른 괄호 문자열을 만들 수 있으면 첫째 줄에 Yes를, 만들 수 없으면 No를 출력한다. 따옴표는 출력하지 않는다.

예제5

예제 1
입력
```
3
()(()((
))()()(()
)())(())
```
예상 출력
```
Yes
```
예제 2
입력
```
2
))()((
))((())(
```
예상 출력
```
No
```
예제 3
입력
```
1
()
```
예상 출력
```
Yes
```
예제 4
입력
```
1
)(
```
예상 출력
```
No
```
예제 5
입력
```
2
((
))
```
예상 출력
```
Yes
```