FIXPAREN 문제 질문입니다....

  • wlgns5721
    wlgns5721
    #include<string>
    #include<iostream>
    #include<vector>
    using namespace std;
    
    class FixParen {
    private:
        vector <char> priority_vec;
        vector <int> paren_vec;
    public:
        void Input_data() {    //데이터를 입력 받고,벡터에 삽입
            priority_vec.clear();
            paren_vec.clear();
            string a, b;
            cin >> a >> b;
            for (int i = 0; i < b.size(); i++) 
                priority_vec.push_back(b.at(i));
            for (int i = 0; i < priority_vec.size(); i++) {
                if (priority_vec[i] == '<')
                    priority_vec.push_back('>');
                else if (priority_vec[i] == '{')
                    priority_vec.push_back('}');
                else if (priority_vec[i] == '[')
                    priority_vec.push_back(']');
                else if (priority_vec[i] == '(')
                    priority_vec.push_back(')');
    
            }
            for (int i = 0; i < a.size(); i++) {
                for (int s = 0; s < priority_vec.size()/2; s++) {
                    if (a.at(i) == priority_vec[s]) {
                        paren_vec.push_back(s+1);
                        break;
                    }
                }
                for (int s = (priority_vec.size() / 2); s < priority_vec.size(); s++) {
                    if (a.at(i) == priority_vec[s]) {
                        paren_vec.push_back(-s - 1 + priority_vec.size()/2);
                        break;
                    }
                }
            }
        }
    
        void Fix() {
    
            int count = 0;
            int count_of_count = 1;
            for (int i = 0; i < paren_vec.size(); i++) {
                if (paren_vec[i] > 0) {
                    count++;
                }
                else if (paren_vec[i] < 0 && count == 0)
                    continue;
    
                else {
    
                    if (paren_vec[i] + paren_vec[i - count_of_count] > 0)
                        paren_vec[i - count_of_count] = -paren_vec[i];
                    else if ((paren_vec[i] + paren_vec[i - count_of_count] < 0))
                        paren_vec[i] = -paren_vec[i - count_of_count];
    
                    count_of_count += 2;
                    count--;
                    if (!count)
                        count_of_count = 1;
    
    
                }
            }
        }
    
        void OutPutPrint() {
            for (int i = 0; i < paren_vec.size(); i++) {
                for (int s = 0; s < priority_vec.size()/2; s++) {
                    if (paren_vec[i] - 1 == s)
                        cout << priority_vec[s];
                }
                for (int s = priority_vec.size()/2; s < priority_vec.size(); s++) {
                    if (priority_vec.size()/2 - (paren_vec[i] + 1) == s)
                        cout << priority_vec[s];
                }
            }
            cout << endl;
        }
    };
    
    
    int main() {
        int T;
        cin >> T;
        for (int i = 0; i < T; i++) {
            FixParen fix;
            fix.Input_data();
            fix.Fix();
            fix.OutPutPrint();
        }
    
        return 0;
    }
    

    문제링크는 FIXPAREN 입니다.

    알고리즘을 대략적으로 설명하면, 예를들어 인자를 ()<{]] <({[ 이렇게 두개를 입력받았다고 하면

    먼저 Input_Data() 함수에서 두번째 인자를 priority_vec 벡터에 < , ( , { , [ 하나씩 삽입합니다. 이때 왼쪽 괄호를 먼저 넣고 오른쪽 괄호도 우선순위대로 넣습니다.
    이후에 첫번째 인자 ()<{]]를 paren_vec에 삽입을 하는데, 문자를 하나씩 삽입하는게 아니라 우선순위 숫자를 삽입합니다.
    예를 들어 <는 우선순위가 가장 높으니 1이고 {는 3번째이기 때문에 3입니다. 또한 반대 괄호 같은 경우는 같은 값의 음수를 넣어줍니다. 즉, paren_vec에는 2 , -2 , 1 , 3 , -4 , -4 이런식으로 들어갑니다.

    그리고 Fix 함수에서 괄호를 우선순위에 맞춰서 조정을 하는데,
    첫번째 인자 ()<{]] 각각의 괄호를 숫자로 변환해서 넣은 priority_vec을 반복문을 돌려서 하나씩 값을 검사합니다. 만약 양수라면 왼쪽 괄호라는 뜻이므로 count++을 해줍니다. 그러다가 오른쪽 괄호를 만나면 그 오른쪽 괄호와 짝이 되는 왼쪽 괄호를 찾아서 두개를 서로 더합니다. 만약 0이라면 둘이 같은 괄호이므로 그대로 지나가고 양수 값이라고 하면 왼쪽괄호가 우선순위가 낮으므로(우선순위가 낮을수록 값이 크므로) 왼쪽괄호를 바꿔주고 0보다 작으면 오른쪽 괄호를 바꿉니다. count수만큼 반복합니다. count_of_count는 오른쪽 괄호가 왼쪽 괄호를 찾기 위한 변수입니다.
    마지막으로 OutPutPrint로 숫자로 변환한 값들을 다시 괄호로 변환해서 출력합니다.

    설명이 좀 긴거 같은데 요약하자면
    1. 두 인자를 받고, 두번째 인자는 priority_vec에 삽입, 오른쪽 괄호도 우선순위대로 추가적으로 삽입.

    1. paren_vec에 괄호를 숫자로 변환하여 삽입, 오른쪽 괄호는 음수값

    2. for 문으로 paren_vec를 하나씩 검사하는데, 양수값이면 count++

    3. 만약 음수값이면 오른쪽괄호라는 뜻으로 그에 해당하는 왼쪽 괄호를 찾아 두개를 더함. 만약 0이면 두개는 같은 괄호, 양수면 왼쪽이 우선순위가 낮으므로 왼쪽을 바꾸고, 음수면 오른쪽을 바꿈

    4. 마지막으로 숫자로 된 paren_vec을 문자로 변환하여 출력

    이렇게 코딩을 했는데, 오답이 뜨네요.... 어떤 케이스에서 오답이 나는 걸까요 ㅠㅠ 아무리 테스트해봐도 틀린 케이스를 못찾겠는데 왜 오답이 나는걸까요 ㅠㅠ


    8년 전
2개의 댓글이 있습니다.
  • seico75
    seico75

    ((>(>) <({[
    위 경우가 잘 되는지 확인해보세요.
    그리고,
    for (int i = 0; i < priority_vec.size(); i++) {}
    이 루프가 몇번 돌까요?
    4번이 아닌 8번 돌텐데 결과에는 상관이 없겠지만 원하는 바는 아닐 것이라는 생각이 드네요.


    8년 전 link
  • wlgns5721
    wlgns5721

    오! 이런 케이스가 있군요. 왜 생각을 못했지 ㅠㅠ 감사합니다!


    8년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.