'리트코드 20번'에 해당되는 글 1건

문제 :

문자열 s가 '(', ')', '{', '}', '[', ']' 문자만 포함하고 있을 때, 이 문자열이 유효한지 판단하세요.

문자열이 유효하려면 다음 조건을 모두 만족해야 합니다:

• 열린 괄호는 동일한 종류의 닫는 괄호로 닫혀야 합니다.
• 열린 괄호는 올바른 순서로 닫혀야 합니다.
• 모든 닫는 괄호는 대응되는 동일한 종류의 열린 괄호를 가져야 합니다.

예시:

예시 1:

입력: s = "()"
출력: true

예시 2:

입력: s = "()[]{}"
출력: true

예시 3:

입력: s = "(]"
출력: false

예시 4:

입력: s = "([])"
출력: true

제약 사항:

• 1 ≤ s.length ≤ 10⁴
• s는 오직 괄호 문자 '()[]{}' 로만 구성됩니다.

구현 :

이 문제의 힌트를 보았을 때,

1. 문자 스택을 쓰고

2. (, {, [ 등 열린 괄호를 만나면 스택에 넣고

3. ), }, ] 닫힌 괄호를 만나면 스택에서 매칭되는 열린괄호가 있으면 pop하라고 했다.

class Solution {
    public boolean isValid(String s) {
		// 스택 준비
        Stack<Character> stack = new Stack<>();
        // 매칭되는 괄호를 찾기 위해 HashMap 준비
        Map<Character, Character> mapping = new HashMap<>();
        mapping.put(')', '(');
        mapping.put('}', '{');
        mapping.put(']', '[');
		
        // String s를 문자 배열로 전환하여 하나씩 
        for (char c : s.toCharArray()) {
        	// 열린 괄호가 들어오면 stack에 푸시
            if (mapping.containsValue(c)) {
                stack.push(c);
            // 닫힌 괄호가 들어오면 실행
            } else if (mapping.containsKey(c)) {
            	// 스택이 비어 있거나 가장 마지막에 들어온 값을 pop해서 비교
                if (stack.isEmpty() || mapping.get(c) != stack.pop()) {
                	// 매칭되는 괄호가 아니면 false 리턴
                    return false;
                }
            }
        }

        return stack.isEmpty();  

    }
}