올바른 괄호 문제 풀이

괄호가 ()로 바르게 짝지어졌으면 올바른 괄호 true 반환 그렇지 않으면 false 반환 

boolean solution(String s) {

boolean answer = true;

Stack<Character> stack = new Stack<>();

if(s.startsWith(")")||s.endsWith("(")||s.length()%2==1)return false;

char[] arr = s.toCharArray();

for(int i=0; i<arr.length;i++){

if(!stack.isEmpty()&&stack.peek()=='('&&arr[i]==')')stack.pop();

else stack.add(arr[i]);

}

if(stack.size()!=0)answer=false;

return answer;

}

stack의 peek 메소드로 맨 위 문자를 확인하여 ( 이고 다음 넣을 원소가 ) 이면 stack에서 꺼내고 

마지막에 스택이 비었으면 올바른 괄호인다. 

 

테스트 케이스는 통과하지만 효율성 검사에서 시간초과로 실패한다. 

)로 시작하거나 (로 끝나거나 문자의 개수가 홀수이면 짝을 지을 수 없어 계산할 필요 없이 false 반환하게 하였더니 성공 

 

boolean solution2(String s) {

boolean answer = false;

int count = 0;

for(int i = 0; i<s.length();i++){

if(s.charAt(i) == '('){

count++;

}

if(s.charAt(i) == ')'){

count--;

}

if(count < 0){

break;

}

}

if(count == 0){

answer = true;

}

return answer;

}

스택을 사용하지 않고 배열로만 문제를 푸는 방법 

count가 음수가 된다는 것은 위에서 )로 시작한다는 것과 같은 이야기이다.