[HackerRank] Balanced Brackets

Problem

---

A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].

Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or {) occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: [], {}, and ().

A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[(])} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].

By this logic, we say a sequence of brackets is balanced if the following conditions are met:

• It contains no unmatched brackets.
• The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.

Given  strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES. Otherwise, return NO.

Function Description

Complete the function isBalanced in the editor below.

isBalanced has the following parameter(s):

• string s: a string of brackets

Returns

• string: either YES or NO

Input Format

The first line contains a single integer n, the number of strings.
Each of the next n lines contains a single string s, a sequence of brackets.

Constraints

• 1 ≤ n ≤ 10³
• 1 ≤  |s| ≤  10³, where |s| is the length of the sequence.
• All chracters in the sequences ∈ { {, }, (, ), [, ] }.

Output Format

For each string, return YES or NO.

Sample Input

STDIN Function 
----- --------
3
{[()]}
{[(])}
{{[[(())]]}}

Sample Output

YES
NO
YES

Explanation

 

1. The string {[()]} meets both criteria for being a balanced string.
2. The string {[(])} is not balanced because the brackets enclosed by the matched pair { and } are not balanced: [(]).
3. The string {{[[(())]]}} meets both criteria for being a balanced string.

---

괄호는 다음 문자 중 하나로 간주됩니다: (, ), {, }, [, ].

두 괄호는 다음과 같은 조건을 만족하면 맞는 쌍으로 간주됩니다: 동일한 종류의 여는 괄호((, [, {)가 해당 닫는 괄호(), ], })의 왼쪽에 위치합니다. 괄호에는 세 가지 종류의 맞는 쌍이 있습니다: [], {}, ().

괄호 쌍이 불균형인 경우는 괄호 쌍이 닫혀 있는 중간의 괄호들이 맞지 않는 경우입니다. 예를 들어, {[(])}는 불균형입니다. 이는 {와 } 사이의 내용물이 균형이 맞지 않기 때문입니다. 예를 들어, 대괄호 쌍은 여는 괄호 ( 하나만을 포함하고 있고, 소괄호 쌍은 닫는 대괄호 ] 하나만을 포함하고 있습니다.

이 논리에 따라 괄호 시퀀스가 균형을 이루었다고 하려면 다음 조건을 충족해야 합니다:

1. 모든 괄호가 맞는 쌍으로 이루어져야 합니다.
2. 맞는 괄호 쌍 안에 포함된 괄호들의 부분 집합도 맞는 쌍으로 이루어져야 합니다.

주어진 문자열이 균형을 이루는지 확인하는 함수 isBalanced를 작성하세요. 문자열이 균형을 이루면 "YES"를 반환하고, 그렇지 않으면 "NO"를 반환합니다.

 

함수 설명

함수를 아래와 같이 작성하세요:

• 함수 이름: isBalanced
• 파라미터: string s - 괄호 시퀀스가 포함된 문자열
• 반환값: 문자열 YES 또는 NO

입력 형식

• 첫 번째 줄에는 문자열의 개수 n이 주어집니다.
• 다음 n개의 줄에는 각각 괄호 시퀀스를 나타내는 문자열 s가 주어집니다.

제약 사항

• 1 ≤ n ≤ 10³
• 1≤ |s| ≤ 10³ , 여기서 |s|는 괄호 시퀀스의 길이입니다.
• 모든 문자는 {, }, (, ), [, ] 중 하나입니다.

출력 형식

각 문자열에 대해 "YES" 또는 "NO"를 반환합니다.

728x90

 

 

 

 

Solution

---

주어진 조건을 만족하는 isBalanced 함수 코드입니다. 스택을 사용하여 여는 괄호를 넣고, 닫는 괄호를 만났을 때 스택에서 상단 요소와 비교하여 짝이 맞는지 확인합니다.

class Result {

    /*
     * Complete the 'isBalanced' function below.
     *
     * The function is expected to return a STRING.
     * The function accepts STRING s as parameter.
     */

    public static String isBalanced(String s) {
        Stack<Character> stack = new Stack<>();

        for (char ch : s.toCharArray()) {
            // 여는 괄호를 스택에 추가
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                // 닫는 괄호가 스택의 상단 요소와 맞는 쌍인지 확인
                if (stack.isEmpty()) {
                    return "NO";
                }
                char top = stack.pop();
                if ((ch == ')' && top != '(') ||
                    (ch == '}' && top != '{') ||
                    (ch == ']' && top != '[')) {
                    return "NO";
                }
            }
        }
        
        // 스택이 비어 있으면 균형이 맞음
        return stack.isEmpty() ? "YES" : "NO";
    }
}

 

1. 스택 생성: 괄호의 균형을 맞추기 위해 스택을 생성합니다.
2. 여는 괄호 처리: (, {, [ 같은 여는 괄호가 나오면 스택에 추가합니다.
3. 닫는 괄호 처리: ), }, ] 같은 닫는 괄호가 나오면 스택의 상단 요소와 맞는 쌍인지 확인합니다.
   • 스택이 비어 있다면 균형이 맞지 않으므로 바로 "NO"를 반환합니다.
   • 상단 요소와 닫는 괄호가 맞지 않으면 "NO"를 반환합니다.
4. 결과 반환: 모든 괄호를 처리한 후 스택이 비어있다면 모든 괄호가 균형이 맞으므로 "YES"를 반환하고, 그렇지 않다면 "NO"를 반환합니다.

이 코드는 O(n)의 시간 복잡도를 가지며, 문자열의 길이가 크더라도 효율적으로 처리할 수 있습니다.

---

 

1. Stack<Character> stack = new Stack<>();
   • 설명: 스택은 LIFO (Last In, First Out) 구조로, 가장 최근에 추가된 요소가 먼저 제거됩니다. 괄호의 여닫는 순서를 체크하기에 적합합니다.
   • 기능: 여는 괄호가 나올 때마다 스택에 추가하고, 닫는 괄호가 나올 때는 스택에서 제거하여 쌍을 이루는지 확인합니다.
2. for (char ch : s.toCharArray())
   • 설명: 문자열 s의 각 문자를 하나씩 순회하는 반복문입니다.
   • 기능: 문자열을 문자 배열로 변환하여 각 문자(ch)를 하나씩 순회합니다. 이를 통해 문자열의 모든 괄호를 한 번에 처리할 수 있습니다.
3. if (ch == '(' || ch == '{' || ch == '[')
   • 설명: ch가 여는 괄호 중 하나인지 확인합니다.
   • 기능: 여는 괄호인 경우 스택에 추가합니다. 이를 통해 이후의 닫는 괄호와 짝을 맞출 수 있게 됩니다.
4. stack.push(ch);
   • 설명: 여는 괄호를 스택에 추가합니다.
   • 기능: 여는 괄호는 닫는 괄호와 쌍을 이루어야 하기 때문에, 스택에 보관하여 이후에 사용할 수 있도록 합니다.
5. else
   • 설명: ch가 여는 괄호가 아닌 경우로, 닫는 괄호인 경우에 해당합니다.
   • 기능: 닫는 괄호가 나올 때마다, 스택에 쌓여있는 여는 괄호와 쌍을 맞추는 작업을 수행합니다.
6. if (stack.isEmpty())
   • 설명: 스택이 비어 있는지 확인합니다.
   • 기능: 스택이 비어 있는 상태에서 닫는 괄호가 나오면 균형이 맞지 않으므로 바로 "NO"를 반환합니다. 이 경우에는 닫는 괄호에 해당하는 여는 괄호가 없다는 의미이므로 균형이 맞지 않습니다.
7. char top = stack.pop();
   • 설명: 스택의 최상단 요소를 제거하고 그 값을 top 변수에 저장합니다.
   • 기능: 현재의 닫는 괄호와 쌍을 이루는 여는 괄호가 맞는지 확인하기 위해 최상단에 저장된 여는 괄호를 꺼내옵니다.
8. if ((ch == ')' && top != '(') || (ch == '}' && top != '{') || (ch == ']' && top != '['))
   • 설명: ch가 닫는 괄호일 때, 꺼낸 top이 올바른 쌍인지 확인합니다.
   • 기능: 닫는 괄호와 여는 괄호가 일치하지 않으면 균형이 맞지 않으므로 "NO"를 반환합니다. 예를 들어 ch가 )인데 top이 (가 아니라면 균형이 맞지 않는 것입니다.
9. return stack.isEmpty() ? "YES" : "NO";
   • 설명: 모든 문자를 처리한 후 스택이 비어 있는지 확인합니다.
   • 기능: 스택이 비어 있다면 모든 여는 괄호가 맞는 닫는 괄호와 짝을 이룬 것이므로 균형이 맞는 것으로 간주하고 "YES"를 반환합니다. 스택에 여전히 여는 괄호가 남아 있으면 짝이 맞지 않으므로 "NO"를 반환합니다.