오늘 풀어본 문제는 프로그래머스에 있는 올바른 괄호라는 문제이다.
문제의 설명은 다음과 같다.
문제 설명
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
- 문자열 s의 길이 : 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
해당 문제는 '('가 나오면 뒤에 무조건')'가 나와야 true가 된다.
문제를 푼 코드는 다음과 같다.
import java.util.Stack;
class Solution {
boolean solution(String s) {
boolean answer = true;
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++){
char ch = s.charAt(i);
if (ch == '('){
stack.push(ch);
} else {
if (stack.isEmpty()){
answer = false;
break;
}
stack.pop();
}
}
if (stack.size() != 0){
answer = false;
}
return answer;
}
}이 문제는 전형적인 스택을 이용해서 푸는 문제로 앞 괄호가 나오면 스택에 넣어주고 뒤 괄호가 나오면 스택을 스택에 맨 위에 존재하는 값을 제거해준다.
근데 여기서 한 가지 조건이 존재하는데 뒤 괄호가 나왔을 때 스택이 비어있으면 answer를 false로 만들어주고 반복을 종료한다.
그 이유는 뒤 괄호가 나왔는데 스택이 비어있다는 의미는 뒷괄호와 짝인 앞 괄호가 없다는 의미이다.
그리고 만약 반복이 모두 종료되고 나서 스택이 비어있지 않으면 그 괄호 또한 짝이 존재하지 않는다는 의미이기 때문에 이 또한 answer를 false로 만들어준다.
Stack이란
스택(Stack)은 "쌓다"라는 의미로, 데이터를 차곡차곡 쌓아올린 형태의 자료구조이다. 조금 더 설명하자면, 데이터가 순서대로 쌓이며 가장 마지막에 삽입된 자료가 가장 먼저 삭제되는 구조를 가지고 있다.
스택은 정해진 방향으로만 쌓을 수 있으며, top으로 정한 곳을 통해서만 접근할 수 있다. 새로 삽입되는 자료는 top이 가리키는 가장 맨 위에 쌓이게 되며, 자료를 삭제할 때도 top을 통해서 삭제가 가능하다.
그리고 스택에서는 삽입 연산을 push, 삭제 연산을 pop이라고 하며, 이러한 스택의 구조를 후입 선출의 구조라고 하며, 줄여서 LIFO(Last In First Out)라고 부른다.
