[LeetCode] Valid Parentheses

https://leetcode.com/problems/valid-parentheses/description/

 

[문제]

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

 

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

 

Constraints:

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

올바른 괄호 형식인지 검사하는 문제로 스택(Stack)을 이용하는 대표적인 알고리즘 문제 중 하나이다.

 

 

풀이 방법

1. 빈 스택을 한 개 정의한다.
2. 입력받은 String을 character 별로 순회한다.
3. 만약 현재의 character가 여는 괄호라면 스택에 push한다.
4. 아니라면, (닫는 괄호라면) 스택이 비어있는지 확인한다. 비어있을 경우 닫는 괄호와 매칭되는 여는 괄호가 없다는 뜻이므로 false를 반환한다. 비어있지 않을 경우 top 원소를 pop 시킨 후 닫는 괄호와 매칭되는 여는 괄호인지 확인한다. 아니라면 false를 반환한다.
5. String을 전부 돈 후 스택이 비어있을 경우 true를 반환, 아니라면 false를 반환한다. 

 

복잡도

시간 복잡도 : O(n), n이 string의 길이라고 했을 때 하나씩 돌며 상수 시간 동작을 수행하기 때문에.

공간 복잡도 : O(n), 최악의 경우 n이 전부 push 되므로

 

 

[코드]

public boolean isValid(String s) {
	Stack<Character> stack = new Stack<Character>();
	for (char c : s.toCharArray()) {
		if (c == '(')
			stack.push(')');
		else if (c == '{')
			stack.push('}');
		else if (c == '[')
			stack.push(']');
		else if (stack.isEmpty() || stack.pop() != c)
			return false;
	}
	return stack.isEmpty();
}

 

나는 여는 괄호라면 ('(' or '{' or '[') stack에 해당 값을 push 하고 나중에 pop한 후 (이면 )인지, {라면 }인지 하나 하나 직접 비교하며 검증하는 방식으로 풀었다. 위는 더 깔끔하고 쉬운 코드로, 여는 괄호를 만나면 해당 값이 아닌 닫는 괄호를 push해서 나중에 닫는 괄호를 만났을 때 같은 타입의 괄호인지 검증하지 않고 그냥 같은지 아닌지만 검사하면 된다.