[LeetCode- Ch7. DFS & BFS] 6. 유효하지 않은 괄호 제거

 

https://leetcode.com/problems/remove-invalid-parentheses/

Remove Invalid Parentheses - LeetCode

 

1. 문자열에서 쌍으로 존재하는 괄호만 리턴하는데, 가능한 경우의 수 모두를 담아서 리턴

 

2. 유효하지 않는 괄호는 제거한다.

 

문제 해결 순서

1. Queue에 저장
2. 케이스별로 유효성 체크
3. 쌍으로 존재하는지 체크해, 해당하는 문자열을 새로운 큐에 저장

유효한 괄호 확인 메서드

1. 스택을 이용
2. count를 이용

 

1. 스택 이용

private boolean isValid(String s){
    Stack<Character> stack = new Stack<>();
    for(char x : s.toCharArray()){
        if(x!='('&& x!=')'){
            continue;
        }else if(x==')' && stack.isEmpty()){
            return false;
        }else if(x=='('){
            stack.push(x);
        }else if(x==')' && stack.peek()=='('){
            stack.pop();
        }
    }
    if(stack.isEmpty()){
        return true;
    }else{
        return false;
    }
}

 

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        //모든 괄호를 빼보고, 맞는지 확인 후 추가
        List<String> res= new ArrayList<>();
        
        if(s==null){
            return res;
        }
        Queue<String> q = new LinkedList<>();
        Set<String> visited= new HashSet<>();
        q.offer(s);
        visited.add(s);
        //주어진 문자열이 n자리면, 해답은 n-1자리 문자열으 BFS 종료조건 생성
        boolean found=false;
        
        //큐 반복
        while(!q.isEmpty()){
            int size=q.size();
            for(int i=0;i<size;i++){
            String tmp = q.poll();
                //처음은 반드시 유효하지 않은 괄호이므로
                if(isValid(tmp)){
                    res.add(tmp);
                    found=true;
                }
                //for문이 한번만 돌게 하기 위해서
                if(found) continue;
                
                //n개에서 n-1개가 되는, 처음만 돈다.
                for(int j=0;j<tmp.length();j++){
                    if(tmp.charAt(j)!='(' && tmp.charAt(j)!=')') continue;
                    String newStr= tmp.substring(0, j) + tmp.substring(j+1);
                    if(!visited.contains(newStr)){
                        q.offer(newStr);
                        visited.add(newStr);
                    }
                }
            }
        }
        
        
        return res;
    }
    private boolean isValid(String s){
        Stack<Character> stack = new Stack<>();
        for(char x : s.toCharArray()){
            if(x!='('&& x!=')'){
                continue;
            }else if(x==')' && stack.isEmpty()){
                return false;
            }else if(x=='('){
                stack.push(x);
            }else if(x==')' && stack.peek()=='('){
                stack.pop();
            }
        }
        if(stack.isEmpty()){
            return true;
        }else{
            return false;
        }
    }
}

 

2. count 이용

public boolean isValid(String s){
   int count=0;
    for(char c:s.toCharArray()){
        if(c=='('){
            count++;
        }else if(c==')'){
            count--;
            if(count<0) return false;
        }
    }
    return count==0;
}

-> return count==0; -> count==0이면 true, 아니면 false 출력

 

class Solution {
    public List<String> removeInvalidParentheses(String s) {
        List<String> res= new ArrayList<>();
        Set<String> set = new HashSet<>();
        boolean flag=false;
        Queue<String> q = new LinkedList<>();
        q.offer(s);
        while(!q.isEmpty()){
            int size=q.size();
            for(int i=0;i<size;i++){
            String str= q.poll();
                if(isValid(str)){
                    res.add(str);
                    flag=true;
                }
                if(flag) continue;
                
                for(int j=0;j<str.length();j++){
                    if(str.charAt(j)!='(' &&str.charAt(j)!=')') continue;
                    String newStr=str.substring(0, j)+str.substring(j+1);
                    if(!set.contains(newStr)){
                        set.add(newStr);
                        q.offer(newStr);
                    }
                }
            }
        }
        return res;
    }
    public boolean isValid(String s){
       int count=0;
        for(char c:s.toCharArray()){
            if(c=='('){
                count++;
            }else if(c==')'){
                count--;
                if(count<0) return false;
            }
        }
        return count==0;
    }
}