algospot.com :: 질문과 답변: 안녕하세요 DECUAL 문제 질문 있습니다.

안녕하세요 DECUAL 문제 질문 있습니다.

접근 방법이 잘못되었는지.. 계속 시간초과가 나서 질문드립니다.

저의 시도 방법은 압축된 두 문자열을 원본 길이 만큼 모든 문자를 비교 하는 것입니다. (압축은 풀지 않습니다.)

ex) C(O)^2KIE(RUN)^5, COOKIER(UNR)^4UN
두 문자열의 0 번째 문자(C) 부터 시작하여 원본 길이 만큼 인덱스를 증가 시키며 모든 문자들을 비교 합니다.
중간에 다른 문자가 있으면 결과를 NO 로 하고 즉시 리턴합니다. 원본 길이 만큼 비교 했다면 두 문자열을 같다고 판단합니다.

위 과정을 수행 하기 전 사전체크를 합니다.

압축 된 문자열이 같으면 YES. ;;
압축을 풀었을 때 전체 길이를 계산 : 원본 문자열의 길이가 다르면 다른 문자열로 판단하여 NO
알파벳 등장 횟수 확인 : 원본 문자열의 길이가 같더라도 알파벳(A~Z) 각각의 등장횟수가 다르면 다른 문자열로 간주 하여 NO.

그리고 중복 되는 비교를 없애기 위해 아래와 같이 처리했습니다.

같은 문자열의 반복이 있으면 건너 뛴다.
ex1) A^2(ABC)^10000DE, AA(ABC)^100000DE
(ABC)^100000는 같은 위치에서 반복 되므로 건너 뛰고 DE를 확인.
ex2) A(AAA)^100000000AB, (AAA)^100000000AAB
(AAA)^100000000 은 결과에 영향을 미치지 않으므로 건너뛴다.

접근방법이 잘못 된 것일까요.. 놓친 부분이 있는 것일까요.. 조언부탁드립니다.

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stdio.h>
using namespace std;

using preCheck = pair<long long, vector<long long>>;
using partialCheck = pair<long long, string>;

class AcmStringComparator
{
public:
    AcmStringComparator(string str1, string str2);
    bool getResult();
protected:
    bool result;
    preCheck calculateOriginLength(string str);
    partialCheck checkPartiallyEquals(const char* str1, const char* str2);
};

AcmStringComparator::AcmStringComparator(string str1, string str2)
{
    result = false;

    if (str1 == str2) {
        result = true;
        return;
    }

    preCheck preCheck1 = calculateOriginLength(str1);
    preCheck preCheck2 = calculateOriginLength(str2);

    if (preCheck1.first == 0 || preCheck2.first == 0) return;
    if (preCheck1.first != preCheck2.first) return;
    if (preCheck1.second != preCheck2.second) return;
    else {
        for (long long l : preCheck1.second) {
            if (l != 0) {
                if (l == preCheck1.first) {
                    result = true;
                    return;
                }
                break;
            }
        }
    }

    const char * pStr1 = str1.c_str();
    const char * pStr2 = str2.c_str();

    long long outIter = 1;

    long long iter1 = 0;
    const char * pStart1 = nullptr;
    const char * pNextStart1 = nullptr;

    long long iter2 = 0;
    const char * pStart2 = nullptr;
    const char * pNextStart2 = nullptr;

    bool isIniter1 = false;
    bool isIniter2 = false;

    bool musi1 = false;
    bool musi2 = false;

    while(true) {

        if ((musi1 == true && *pStr1 == ')')) {
            while (true) {
                if ((*pStr1 % 65) >= 0 && (*pStr1 % 65) <= 25) {
                    break;
                }
                pStr1++;
            }
            musi1 = false;
        }
        if ((musi2 == true && *pStr2 == ')')) {
            while (true) {
                if ((*pStr2 % 65) >= 0 && (*pStr2 % 65) <= 25) {
                    break;
                }
                pStr2++;
            }
            musi2 = false;
        }

        if (*pStr1 == '(') {
            isIniter1 = true;
            pStr1++;
            pStart1 = pStr1;
            continue;
        }

        if ((iter1 == 0) && (*pStr1 == ')')) {
            const char* p = pStr1 + 2;
            char strIter[9] = { 0 };

            for (int i = 0; i < 10; ++i) {
                if (i < 10 && ( (*p >= 48) && (*p <= 57) )) {
                    strIter[i] = *p;
                    p++;
                }
                else {
                    iter1 = atoi(strIter);
                    pStr1 = pStart1;
                    pNextStart1 = p;
                    break;
                }
            }
            isIniter1 = false;
        }
        else if ((iter1 != 1) && (*pStr1 == ')')) {
            pStr1 = pStart1;
            iter1--;
            isIniter1 = false;
        }

        if (iter1 == 1) {
            pStr1 = pNextStart1;
            iter1--;
            continue;
        }

        if (*pStr2 == '(') {
            isIniter2 = true;
            pStr2++;
            pStart2 = pStr2;
            continue;
        }

        if ((iter2 == 0) && (*pStr2 == ')')) {
            const char* p = pStr2 + 2;
            char strIter[9] = { 0 };

            for (int i = 0; i < 10; ++i) {
                if (i < 10 && ((*p >= 48) && (*p <= 57))) {
                    strIter[i] = *p;
                    p++;
                }
                else {
                    iter2 = atoi(strIter);
                    pStr2 = pStart2;
                    pNextStart2 = p;
                    break;
                }
            }
            isIniter2 = false;
        }
        else if ((iter2 > 1) && (*pStr2 == ')')) {
            pStr2 = pStart2;
            iter2--;
            isIniter2 = false;
        }

        if (iter2 == 1) {
            pStr2 = pNextStart2;
            iter2--;
            continue;
        }

        if (isIniter1 == true && isIniter2 == true) {
            const char* pTmp1 = pStr1;
            const char* pTmp2 = pStr2;

            while (true) {
                if (*pTmp1 == '(') {
                    break;
                }
                pTmp1--;
            }
            while (true) {
                if (*pTmp2 == '(') {
                    break;
                }
                pTmp2--;
            }
            partialCheck ptc = checkPartiallyEquals(pTmp1 + 1, pTmp2 + 1);

            if (ptc.first != 0) {
                musi1 = true;
                musi2 = true;
            }
            isIniter1 = false;
            isIniter2 = false;

            //같은지 확인.
        }

        if ((*(pStr1 - 1) == '(') && (*(pStr2 - 1) == '(')) {
            partialCheck ptc = checkPartiallyEquals(pStr1, pStr2);
            if (ptc.first != 0) {
                outIter += ptc.first * ptc.second.length();
                string rno(to_string(ptc.first));
                pStr1 += rno.length() + ptc.second.length() + 2;
                pStr2 += rno.length() + ptc.second.length() + 2;
                continue;
            }
        }

        if (*pStr1 == 0 && *pStr2 == 0) {
            result = true;
            break;
        }

        //문자 비교
        if (*pStr1 == *pStr2) {


            pStr1++;
            pStr2++;

            if (preCheck1.first == outIter) {
                result = true;
                break;
            }
            else
                outIter++;
        }
        else
            break;
    }

}

partialCheck AcmStringComparator::checkPartiallyEquals(const char* str1, const char* str2) {

    istringstream strm1(str1);
    string token1;
    getline(strm1, token1, '^');

    long long repeatNum = 0;
    strm1 >> repeatNum;

    istringstream strmToken(token1);
    getline(strmToken, token1, ')');

    istringstream strm2(str2);
    string token2;
    getline(strm2, token2, '^');

    long long repeatNum2 = 0;
    strm2 >> repeatNum2;

    istringstream strmToken2(token2);
    getline(strmToken2, token2, ')');

    if (repeatNum == repeatNum2 && token1 == token2) {
        return move(make_pair(repeatNum, token1));
    }

    return  move(make_pair(0, ""));
}

bool AcmStringComparator::getResult() {
    return result;
}

preCheck AcmStringComparator::calculateOriginLength(string str)
{
    istringstream strmCompStr(str);
    string token;
    long long repeatNum = 0;

    long long length = 0;

    vector<long long> charCntList(26, 0);

    while (getline(strmCompStr, token, '(')) {

        length += token.length();
        const char* c = token.c_str();
        for (unsigned int i = 0; i < token.length(); ++i) {
            charCntList[*c % 65]++;
            c++;
        }

        getline(strmCompStr, token, '^');

        repeatNum = 0;
        strmCompStr >> repeatNum;

        istringstream strmToken(token);
        getline(strmToken, token, ')');

        c = token.c_str();

        for (unsigned int i = 0; i < token.length(); ++i) {
            if (repeatNum != 0) {
                long long tmp = charCntList[*c % 65];
                if (tmp == 0) {
                    charCntList[*c % 65] = repeatNum;
                    c++;
                }
                else {
                    charCntList[*c % 65] += repeatNum;
                    c++;
                }
            }
            else
                break;
        }

        length += repeatNum*token.length();
    }

    return make_pair(length, move(charCntList));
}

int main(void)
{
    int testCaseNum = 0;
    cin >> testCaseNum;
    string input1;
    string input2;
    vector<string> output(testCaseNum, "");

    for (int i = 0; i < testCaseNum; ++i) {
        cin.clear();
        cin >> input1;

        cin.clear();
        cin >> input2;

        AcmStringComparator* comp = new AcmStringComparator(input1, input2);

        if ( comp->getResult() )    output[i] = "YES";
        else                        output[i] = "NO";

        delete comp;
    }

    for (auto& str : output)
        cout << str << endl;

    return 0;
}

7년 전

2개의 댓글이 있습니다.

Corea

아래 예제는 잘 나오시나요?
1
A(BCA)^100000000
(ABC)^100000000A

7년 전 link
lullulalal

아 (BCA) 가 길어지면 오래걸리겠네요.. ;;
다시 해보겠습니다.ㅎㅎ

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

SINCE 2007

다가오는 이벤트들

안녕하세요 DECUAL 문제 질문 있습니다.

저의 시도 방법은 압축된 두 문자열을 원본 길이 만큼 모든 문자를 비교 하는 것입니다. (압축은 풀지 않습니다.)

위 과정을 수행 하기 전 사전체크를 합니다.

그리고 중복 되는 비교를 없애기 위해 아래와 같이 처리했습니다.

2개의 댓글이 있습니다.