[알고리즘/java] Stack 스택 (자료구조) / 올바른 괄호

이 글은 인프런 [자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 ] 강의를 수강하며 작성한 글입니다.

- https://inf.run/Azjw

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

문제 :

올바른 괄호 괄호가 입력되면 올바른 괄호이면 “YES", 올바르지 않으면 ”NO"를 출력합니다.

(())() 이것은 괄호의 쌍이 올바르게 위치하는 거지만, (()()))은 올바른 괄호가 아니다.

 

▣ 입력설명 첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.

 

▣ 출력설명 첫 번째 줄에 YES, NO를 출력한다.

 

▣ 입력예제 1

(()(()))(()

 

▣ 출력예제 1

NO

 

 

---

괄호 문제는 스택 자료구조를 활용하는 대표적 문제 중 하나다. 

올바른 괄호란 문제에서 말했다싶이 괄호의 쌍이 올바르게 짝지어진 것을 말한다. 

 

이 문제는 닫는 괄호가 나올 때에는 반드시 여는 괄호가 먼저 나와야 하는 것을 생각하면 왜 스택을 이용하는지 알 수 있다.

 

즉, 닫는 괄호와의 짝을 찾기 위해서는 직전의 여는 괄호를 구해야 하기 때문에 

스택의 LIFO (Last In First Out)원리로 마지막으로 들어간 괄호를 pop 시켜 여는 괄호를 찾는 것이다.

 

 

 

( ( ) ) ( ) 

입력으로 받는 문자열(올바른 괄호)을 예로 보면,

 

 

 

( ( ) ) ( ) 

 

여는 괄호들은 먼저 스택에 push 해 준다.

그럼 스택엔 두 개의 괄호들이 쌓인다.

 

(

(

 

 

( ( ) ) ( ) 

그 다음 닫는 괄호가 나왔을 때에는 바로 직전의 여는 괄호와 짝이 되어야 하므로,

스택에 가장 위에 있는 괄호가 pop 되어 짝이 지어진다.

 

(

 

 

( ( ) ) ( ) 

그 다음은 또 닫는 괄호가 오고, 역시 바로 직전의 여는 괄호와 짝이 되어야 하므로,

스택에 가장 위에 있는 괄호가 pop 되어 짝이 지어진다.

 

 

 

( ( ) ) ( )

그 다음은 여는 괄호이므로 스택에 push 해 준다.

 

(

 

 

( ( ) ) ( )

그 다음은 닫는 괄호이므로 바로 직전의 여는 괄호와 짝이 되어야 하기에

스택에 가장 위에 있는 괄호가 pop 되어 짝이 지어진다.

 

 

 

 

---

 

문자열의 괄호들을 모두 살펴보았을 때, 스택에 남은 괄호가 없다는 것은 결국 모든 괄호들이 올바르게 짝이 지어졌음을 의미한다.

 

반대로 올바르지 않은 괄호의 경우는 짝이 맞지 않았다는 것으로 다음 두 가지 경우가 있다.

1. 닫는 괄호가 나와서 스택의 여는 괄호를 pop해야 하는데 스택이 비어있어 pop할 수 없는 경우

2. 문자열의 괄호를 모두 살펴보았는데, 스택에 여는 괄호가 남아있는 경우

 

 

---

 

< 올바른 괄호 전체코드 >

public class 스택_올바른괄호{

	public static String checkingStr(String str) {
		String answer = "YES";
		Stack<Character> stack = new Stack<>();

		for (char ch : str.toCharArray()) {
			if (ch == '(') { // 여는 괄호면 스택에 push
				stack.push(ch);
			} else { // 닫는 괄호일 경우
				if (stack.isEmpty()) { // 스택이 비어있으면 짝이 될 수 없음.
					return "NO";
				}
				stack.pop(); // 스택이 비어있지 않다면 여는 괄호 pop
			}

		}

		if (!stack.isEmpty()) { 
			/* 문자열 탐색 끝나고 스택이 비어있지 않다면
			 * 여는 괄호가 더 많은 경우임. == 짝 안 맞음.
			 */
			return "NO";
		}

		return answer;
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String str = scan.nextLine();

		System.out.println(checkingStr(str));
	}

}