[PCCP] Lv2: 괄호 회전하기(76502) 해설

문제

- 문제 링크: 괄호 회전하기

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

- N: s의 길이

- 각 문자열을 순회하면 N개의 케이스가 생기고 각 문자열마다 올바른 괄호 여부를 체크하므로 시간 복잡도는 O(N^2)

#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

// 닫힌 괄호의 짝을 바로 확인할 수 있도록 맵 선언
unordered_map<char, char> bracketPair = {{')', '('}, {']', '['}, {'}', '{'}};

// 인수로 받은 문자열 기준 괄호의 짝이 맞는지 확인
bool isValid(string& s, int start) {
    stack<char> stk;
    unsigned int sz = s.size();
    
    // 문자열을 순회하면서
    for (int i = 0; i < sz; ++i) {
        char ch = s[(start + i) % sz];
        // ch가 닫힌 괄호인 경우
        if (bracketPair.count(ch)) {
            // 스택이 비었거나 top 원소가 ch와 짝이 맞는 열린 괄호가 아니면 false 반환
            if (stk.empty() || stk.top() != bracketPair[ch])
                return false;
            // ch와 짝이 맞는 열린 괄호면 해당 열린 괄호 제거
            stk.pop();
        } else {
            stk.push(ch); // 열린 괄호면 스택에 푸시
        }
    }
    // 스택이 비었으면 true를 반환(괄호 짝이 맞다는 의미)
    return stk.empty();
}

int solution(string s) {
    int answer = 0;
    int n = s.size();
    
    // 문자열을 순회하면서 괄호의 짝이 맞으면 answer를 1 증가 시킴
    for (int i = 0; i < n; ++i) {
        answer += isValid(s, i);
    }
    return answer;
}

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- N: s의 길이

- 회전한 괄호 문자열의 유효성을 체크할 때 이중 반복문을 활용: O(N^2)

- 괄호 쌍을 확인할 때 push()와 pop()의 시간 복잡도: O(1)

import java.util.ArrayDeque;
import java.util.HashMap;

class Solution {
    public static int solution(String s) {
        // 괄호 정보를 저장함. 코드를 간결하게 할 수 있음
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');
        
        int n = s.length(); // 원본 문자열의 길이 저장
        s += s; // 원본 문자열 뒤에 원본 문자열을 이어 붙여서 2번 나오도록 만들어줌
        int answer = 0;
        
        // 확인할 문자열의 시작 인덱스를 0 부터 n 까지 이동
        A:for (int i = 0; i < n; i++) {
            ArrayDeque<Character> stack = new ArrayDeque<>();

            // 1번: i(시작 위치)부터 원본 문자열의 길이인 n개까지 올바른 괄호 문자열인지 확인
            for (int j = i; j < i + n; j++) {
                char c = s.charAt(j);
                // HashMap 안에 해당 key 가 없다면 열리는 괄호임
                if (!map.containsKey(c)) {
                    stack.push(c);
                }
                else {
                    // 짝이 맞지 않으면 내부 for문은 종료하고 for문 A로 이동
                    if(stack.isEmpty() || !stack.pop().equals(map.get(c)))
                        continue A;
                }
            }

            // 1번에서 continue 되지 않았고, 스택이 비어있으면 올바른 괄호 문자열임
            if (stack.isEmpty())
                answer++;
        }

        return answer;
    }
}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- N: s의 길이

- 회전한 괄호 문자열의 유효성을 체크할 때 이중 반복문을 활용하므로 시간복잡도: O(N^2)

- 괄호 쌍을 확인할 때 append()와 pop()의 시간복잡도: O(1)

def solution(s):
    answer = 0
    n = len(s)
    for i in range(n):
        stack = []
        for j in range(n):
            # 괄호 문자열을 회전시키면서 참조
            c = s[(i + j) % n]
            if c == "(" or c == "[" or c == "{": # 열린 괄호는 푸시
                stack.append(c)
            else:
                if not stack: # 짝이 맞지 않는 경우
                    break
                
                # 닫힌 괄호는 스택의 top과 짝이 맞는지 비교
                if c == ")" and stack[-1] == "(":
                    stack.pop()
                elif c == "]" and stack[-1] == "[":
                    stack.pop()
                elif c == "}" and stack[-1] == "{":
                    stack.pop()
                else:
                    break
                    
        else: # for문이 break에 의해 끝나지 않고 끝까지 수행된 경우
            if not stack:
                answer += 1
    return answer

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- N: s의 길이

- 회전한 괄호 문자열의 유효성을 체크할 때 이중 반복문을 활용하므로 시간복잡도: O(N^2)

- 괄호 쌍을 확인할 때 push()와 pop()의 시간복잡도: O(1)

function solution(s) {
    const n = s.length;
    let answer = 0;
    
    for (let i = 0; i < s.length; ++i) {
        const stack = [];
        let isCorrect = true;
        for (let j = 0; j < n; ++j) {
            // 괄호 문자열을 회전시키면서 참조
            const c = s[(i + j) % n];
            
            if (c === "[" || c === "(" || c === "{") {
                // 열린 괄호는 무시
                stack.push(c);
            } else {
                if (stack.length === 0) {
                    // 여는 괄호가 없는 경우
                    isCorrect = false;
                    break;
                }
                
                // 닫힌 괄호는 스택의 top과 짝이 맞는지 비교
                const top = stack[stack.length - 1];
                if (c === "]" && top === "[") {
                    stack.pop();
                } else if (c === ")" && top === "(") {
                    stack.pop();
                } else if (c === "}" && top === "{") {
                    stack.pop();
                } else {
                    isCorrect = false;
                    break;
                }
            }
        }
        
        // 모든 괄호의 짝이 맞는 경우
        if (isCorrect && stack.length === 0) {
            answer += 1;
        }
    }
    
    return answer;
}

solution 2)

import

solution 3)

import