[Baekjoon][Java] 9012 괄호

닫는 괄호가 올바른 여는 괄호를 만나는 조건

1. 닫는 괄호의 왼쪽에 있어야 함
2. 아직 짝이 맞지 않아야 함
3. 1,2를 만족하며 가장 오른쪽에 있는 괄호여야 함

시간 복잡도

시간 복잡도 : O($n^2$)

여는 괄호는 그냥 넘어가기에 : O($1$)

닫는 괄호를 찾을 경우에는 운 좋으면 한 번에 할수도 있지만 왼쪽에 있는 모든 괄호를 살펴봐야 함 : O($n$)

총 괄호의 문자열의 길이는 n이기 때문에 지금 이 방법은 O($n^2$)이 된다.

스택을 이용한 풀이

여는 괄호는 스택에 push 하고 닫는 괄호가 나오면 스택에 있는 여는 괄호 하나를 pop한다.

 

입력 : ( ( ) ) ( ) ) 일 경우

 

입력 : (

 

입력 : ( (

 

입력 : ( ( )

 

입력 : ( ( ) )

 

입력 : ( ( ) ) (

 

입력 : ( ( ) ) ( )

 

   

입력 끝 : ( ( ) ) ( ) )

 

닫는 괄호가 마지막에 입력되었지만 스택이 비어있으므로 올바르지 않은 괄호가 된다.