[PGM_76502] 괄호 회전하기 (java)

문제링크

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

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

문제풀이

👨🏻‍💻 핵심 스킬 👨🏻‍💻
 구현

1. 문제 이해

괄호로 이루어진  String이 주어졌을 때 해당 괄호를 회전해서 올바른 괄호가 될 수 있는 경우의 수를 구하는 문제이다.

이 때 회전할 수 있는 크기는 주어진 String의 길이만큼만 가능하다.

 

2. 접근방법

A와 B가 올바른 괄호 문자열이라면 AB도 올바른 괄호 문자열이다. 따라서 우리는 올바른 최소한의 단위의 괄호 문자열들을 구해주면 된다.  String의 길이만큼 회전할 수 있다는 뜻은 한바퀴만 돌 수 있다는 의미와 같다. 따라서 최소단위의 올바른 괄호 문자열들로 이루어진 문자열을 찾아준다면, 그 문자열의 개수만큼이 만들 수 있는 올바른 괄호 문자열의 수가 된다.

 

1. 주어진 String을 한 문자씩 추가하며 최소한의 올바른 괄호의 단위로 쪼개어준다.

2. 만약 String이 모두 올바른 괄호 문자열로 쪼개어진다면 올바른 괄호의 개수가 결과가 된다.

3 만약 올바른 괄호 문자열로 안쪼개어 진다면 한칸씩 회전을 하고 다시 올바른 괄호로 쪼개어준다.(최대 한바퀴가 모두 회전될 때까지 돌아주며 올바른 괄호 문자열을 찾아주면 된다.)

 

3. 구현코드 설명

private String rotate(String s){
    return s.substring(1) + s.charAt(0);
}

한번 회전하는 코드이다. 맨 앞의 괄호를 맨 뒤로 보내어주면 된다.

 

private boolean isPare(Character open, Character close){
    return (open == '{' && close == '}') || (open == '[' && close == ']') || (open == '(' && close == ')');
}

괄호가 올바른지 확인하는 코드이다. 사용에 유의할 점은 여는 괄호와 닫는괄호 순으로 넣어주어야 정상으로 동작한다.

 

private boolean isCorrect(String s){
    Stack<Character> stack = new Stack<>();
    Predicate<Character> isOpen = c -> c == '[' || c == '(' || c == '{';

    for(int i = 0; i < s.length(); i++){
        if(isOpen.test(s.charAt(i)))
            stack.add(s.charAt(i));
        else{
            if(stack.isEmpty() || !isPare(stack.pop(),s.charAt(i)))
                return false;
        }
    }
    if(stack.isEmpty())
        return true;
    else
        return false;
}

주어진 괄호가 올바른지 확인하는 코드이다. Stack을 사용하여 구현하여주었다. 여는 괄호가 들어오면 Stack에 넣어주고 닫는 괄호가 들어올 때 stack에서 꺼내주어 동일한 짝의 괄호이지 확인하며 문제를 해결하였다.

 

 

구현코드

package pgm_76502;

import java.util.Stack;
import java.util.function.Predicate;

public class Solution {
    public int solution(String s) {
        int moveCount = 0; //회전하는 횟수
        int count = 0; // 총 괄호의 수
        while (moveCount != s.length()){ //한 바퀴만 확인
            String check = ""; // 문자단위로 쪼개서 체크
            for(int i = 0; i < s.length(); i++){
                check = check + s.charAt(i);
                if(isCorrect(check)){
                    check = "";
                    count ++;
                }
            }
            if(!check.equals("")) { // 해당 문자열을 모두 확인하였을 때 check가 비어있지 않다면 남은 괄호가 있다는 의미
                count = 0;
                s = rotate(s);
                moveCount++;
            }
            else // 올바른 괄호들로 구성된 문자열
                break;
        }
        return count;
    }

    // 주어진 문자열이 올바른 괄호열인지 확인
    private boolean isCorrect(String s){
        Stack<Character> stack = new Stack<>();
        Predicate<Character> isOpen = c -> c == '[' || c == '(' || c == '{'; // 여는 괄호이면 true

        for(int i = 0; i < s.length(); i++){
            if(isOpen.test(s.charAt(i))) // 여는 괄호는 Stack에 add
                stack.add(s.charAt(i));
            else{
                if(stack.isEmpty() || !isPare(stack.pop(),s.charAt(i))) // 닫는 괄호는 Stack에 있는 여는 괄호와 비교
                    return false; //만약 여는 괄호가 같은 쌍이 아니거나 닫는 괄호가 먼저 나오는 경우
            }
        }
        if(stack.isEmpty()) // 올바른 문자열
            return true;
        else
            return false;
    }

    private boolean isPare(Character open, Character close){ // 같은 쌍인지 비교
        return (open == '{' && close == '}') || (open == '[' && close == ']') || (open == '(' && close == ')');
    }

    private String rotate(String s){ //1회 회전
        return s.substring(1) + s.charAt(0);
    }
}

잘못된 지식이나 궁금한 내용이 있을 경우 편하게 댓글 남겨주시면 감사하겠습니다 :)