문제
괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어
"()()" 또는 "(())()" 는 올바른 괄호입니다.
")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.
'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한사항
문자열 s의 길이 : 100,000 이하의 자연수
문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
❌첫 번재 실패 코드❌
class Solution {
boolean solution(String s) {
boolean answer = true;
int left = 0;
int right = 0;
for(char c : s.toCharArray()){
if(c=='(') left++;
else if(c==')')right++;
}
if(left==right) {
if(s.charAt(0)==')'){
answer=false;
return answer;
}
return answer;
}
else {
answer = false;
return answer;
}
}
}
코드 실행 했을 때 통과해서 행복했으나, 제출 후 채점하기를 누르는 순간 빨간색 글씨와 함께 실패라는 문구가 떴다ㅠㅠ😭😭
한번에 통과되는 적이 없지~!!!!!
일단, 왜 실패가 뜨는지 고민을 해봤다. 아무리 생각해도 모르겠다!!!! 처음 시작하는 괄호가 ) 이면 닫을 수 없기 때문에 그것에 대한 처리도 해줬고.. 개수가 맞지 않으면 '(' 나 ')'가 하나 더 있거나 없다는 것이여서 같을때에만 true를 반환해주고 아닐때에는 false를 반환해주는 처리도 했다..
그럼에도 불구하고 왜 실패라 뜨는걸까..
아무리 고민해도 모르겠어서 검색해봤다. 다른 사람들의 코드와 다른점을 보니 나는
if(left<right){
answer = false;
return answer;
}이 부분이 없었다. 이 부분을 작성해주니 잘 실행 되었다!
그 이유는 if문에서 left와 right가 같을때는 첫번째가 (면 false 아니면 true 그리고 left와 right가 다르면 false를 리턴하게 작성했는데, ())(() 이것처럼 left와 right가 같지만 괄호가 완성되지 않는다. 이것을 처리해주기 위해 (가 앞에 2개 있으면 )가 2개가 있어야하는데 3개가 있으면 그 자리에서 바로 false를 리턴해주는 것이다. 즉 ())까지 보고 (가 )보다 적은 것이 세번째에서 판별이 되어 올바른 괄호가 아니기 때문에 바로 false를 리턴해주는 것이다.
✅성공한 코드
class Solution {
boolean solution(String s) {
boolean answer = true;
int left = 0;
int right = 0;
for(char c : s.toCharArray()){
if(c=='(') left++;
else if(c==')')right++;
if(left<right){
answer = false;
return answer;
}
}
if(left==right) {
if(s.charAt(0)==')'){
answer=false;
return answer;
}
return answer;
}else {
answer = false;
return answer;
}
}
}그리고 검색하면서 알게 된 사실, 이 문제는 stack을 이용해서 풀어야 한다는 것이다ㅠㅠ
일단 스택은 아래 사진처럼 가장 최신에 넣는 데이터가 맨 위쪽에 있고, 제거할 때도 맨 위에 있는 데이터가 먼저 삭제된다.
이 원리를 이용하면 '('가 있을때 push()를 이용해서 스택에 넣고 ')'가 있을때는 스택에 넣은 '('를 pop() 함수를 이용해서 제거한다.
만약에
- ')'로 먼저 시작하거나 '(' 보다 ')'가 더 많거나
- ')'가 '('보다 적을 때
- '('가 없는데 ')'로 인해 pop()해야 할 때
stack은 아무것도 없거나 데이터가 들어있다. 이때 false를 리턴해주면 된다!
✅성공한 코드
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();
}
}
if(stack.size()!=0) return false;
else return true;
}
}Github
