솜이의 데브로그

Programmers ) 괄호 회전 (java) 본문

Algorithm/Programmers

Programmers ) 괄호 회전 (java)

somsoming 2022. 5. 28. 01:07

https://programmers.co.kr/learn/courses/30/lessons/76502

 

코딩테스트 연습 - 괄호 회전하기

 

programmers.co.kr

 

문제

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

  • (), [], {} 는 모두 올바른 괄호 문자열입니다.
  • 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
  • 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {}  ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

 

풀이

괄호 문제는 대부분 stack을 사용해서 푼다.

여기서도 역시 stack을 사용해서 풀고, (, {, [ 와 같이 여는 괄호인 경우에는 push, 닫는 괄호인 경우에는 stack의 top에 있는 값과 확인해서 같은 값이면 pop 하는 방식으로 풀이하면된다.

한칸씩 로테이션하는 방식은 substring을 이용해서 문자열을 재 생성한 다음 체크하는 방식으로 풀이하면 된다.

 

코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = 0;
        for(int i=0; i<s.length(); i++){
            StringBuilder sb = new StringBuilder(s);
            String subString = sb.substring(0, i);
            sb.delete(0, i);
            sb.append(subString);
            if(isString(sb)){
                answer += 1;
            }
        }
        return answer;
    }
    
    public boolean isString(StringBuilder sb) {
        Stack<Character> stack = new Stack<>();
        
        for(int i=0; i<sb.length(); i++){
            if(stack.isEmpty()){
                stack.push(sb.charAt(i));
            } else{
                if(sb.charAt(i) == ']'){
                    if(stack.peek() == '['){
                        stack.pop();
                    } else {
                        stack.push(sb.charAt(i));
                    }
                }else if(sb.charAt(i) == '}'){
                    if(stack.peek() == '{'){
                        stack.pop();
                    } else{
                        stack.push(sb.charAt(i));
                    }
                }else if(sb.charAt(i) == ')'){
                    if(stack.peek() == '('){
                        stack.pop();
                    } else{
                        stack.push(sb.charAt(i));
                    }
                }else{
                    stack.push(sb.charAt(i));
                }
            }
        }
        
        if(stack.isEmpty()) return true;
        else return false;
    }
}

 

 

궁금한점 : stack 내부에 닫는 괄호를 push 할 필요가 있나?