💡 문제
💬 입출력 예시
📌 풀이(소스코드)
import java.util.*;
class Solution {
boolean solution(String s) {
Stack<Character> stack = new Stack<>();
for (char c: s.toCharArray()) {
if (c == '(') {
stack.push(c);
} else {
if (stack.isEmpty()) {
return false;
}
stack.pop();
}
}
return stack.isEmpty();
}
}
📄 해설
접근
- 스택을 사용한 유형 중 대표 유형이라고 생각한다. 간단하게 해결 가능한 문제
- 여는 괄호
(
이면 스택에 푸시하고, 닫는 괄호 )
이면 스택에서 팝을 수행한다.
- 문자열을 순회하는 도중에 비어있으면 올바르지 못한 괄호이므로 바로 종료한다.
- 문자열 순회가 끝났는데 스택이 비어있지 않다면 역시 올바르지 못한 괄호다.
과정
- 문자열
s
를 문자 배열로 변환하기 위해 toCharArray
메소드를 사용하고, 이렇게 변환된 배열을 순회한다. (String.charAt()
을 써도 무방하다.)
- 현재 문자가
(
이면, 스택에 넣고(push) 다음 문자를 확인한다.
- 현재 문자가
)
이면, 아래 작업을 수행한다.
- 현재 스택이 비어있으면
false
를 반환한다. (괄호의 짝이 맞지 않는 것)
- 현재 스택이 비어있지 않으면, 괄호의 짝이 맞으므로 스택의 탑을 꺼내준다.(pop)
- 모든 문자를 확인한 뒤, 스택이 비어있는지에 대한 여부가 정답이된다.
- 비어있으면 모든 괄호가 짝이 맞았으므로, 올바른 괄호 =>
true
- 비어있지 않으면 짝이 맞지 않는 괄호가 있으므로, 올바르지 못한 괄호 =>
false