시간초과라는 건 답은 맞다는 소리인가요???

  • chawoo77
    chawoo77

    안녕하세요.
    이제 막 알고리즘에 발을 디딘 초보입니다.
    지금 BRACKET2라는 문제를 풀고 있는데요.
    전에 짠 소스를 함수로 묶어서 수정하고
    오류가 난 부분도 수정해서 제 컴퓨터에선
    정상적으로 작동하는 프로그램입니다.
    나름 정리도 하고 제대로 해냈다는 만족감에
    얼른 알고스팟에 제출을 했지만....ㅠ;;

    "시간초과"로 퇴짜 맞았어요ㅠ;

    1. 시간초과라는 말은 일단 답은 맞다는 소리인가요?
    2. 보통 1000ms라고 표시하던데 제한시간이 1초라는 소리인가요? (ms라는 단위를 잘 모르겠네요ㅠ 아마 천분의1?;;)
    3. 이 제한시간은 컴파일 시간이 아니라 프로그램실행시간이겠죠?
    4. 아래가 제가 짠 소스인데 아직 초보라 이정도 인데요ㅠ; 제 소스에서 시간이 걸릴 만한 부분이 있나요? 느낌 상으로 반복문이 좀 걸리긴 하지만 그래도 그렇게 많은 반복을 한다고는 생각안들거든요;;

    조언 많이 부탁드리겠습니다.
    감사합니다.

    #include <iostream>
using namespace std;

int num_of_idx;               //먼저 임자 있는 문자 수
int round, curly, square;     //괄호가 열려 있는 문자 수

int strlen(char* str)
{
    int count = 0;
    while (*str++)
        count++;
    return count;
}

//탐색하는 문자가 임자 있는 문자인지 점검하는 함수
bool another(int* idx, int now)
{
    for (int i = 0; i < num_of_idx; i++)
    {
        if (idx[i] == now)
            return true;
    }
    return false;
}

//괄호의 짝을 찾아서 나서는 함수
bool check(char T, char F1, char F2, char* bkt, int i, int* idx)
{
    for (int j = i-1; j >= 0; j -= 2)
    {
        if (another(idx, j))
            continue;              //임자 있으면 지나치기
        if (bkt[j] == F1 || bkt[j] == F2)
            return false;          //맺어질 수 없는 거면 끝!
        if (bkt[j] == T)
        {
            idx[num_of_idx] = j;    //임자 없으면 짝맺어주기
            num_of_idx++;
            return true;
        }
    }
    return false;                  //짝이 없으면 끝!
}


int main(void)
{
    int num;
    cin >> num;

    while (num--)
    {
        char brackets[10001];
        cin >> brackets;

        int index[5000];
        num_of_idx = 0;
        round = 0, curly = 0, square = 0;
        bool result = true;

        //처음 부터 끝가지 검색하는 반복문
        for (int i = 0; i < strlen(brackets); i++)
        {
            if (result == false)
                break;
            if (brackets[i] == '(')
                round++;
            if (brackets[i] == '{')
                curly++;
            if (brackets[i] == '[')
                square++;

            if (brackets[i] == ')') 
            {
                round--;
                result = check('(', '{', '[', brackets, i, index);
            }
            if (brackets[i] == '}') 
            {
                curly--;
                result = check('{', '(', '[', brackets, i, index);
            }
            if (brackets[i] == ']') 
            {
                square--;
                result = check('[', '(', '{', brackets, i, index);
            }
        }
        //괄호의 짝이 맞지 않다면 NO
        if (round != 0 || curly != 0 || square != 0)
            result = false;

        if (result == false)
            cout << "NO\n";
        else
            cout << "YES\n";
    }

    return 0;
}

    11년 전
8개의 댓글이 있습니다.
  • VOCList
    VOCList

    1. 맞는지 틀린지는 모릅니다. 프로그램을 실행하다 제한된 시간 내에 프로그램이 종료되지 않으면 결과를 끝까지 보지 않고 강제로 중지시키기 때문입니다.

    2. 맞습니다.

    3. 맞습니다.

    4. for 문에서 두번째에 들어가는 조건검사문은 루프의 매 바퀴가 시작하기 전에 한번씩 실행되어 해당 루프를 돌지 중지할 것인지를 결정합니다. 따라서 for 문의 조건검사문 안에 strlen을 사용하게 되시면 매번 루프를 돌 때마다 strlen을 호출하게 되는데, strlen의 수행시간은 O(L), L = 문자열의 길이 입니다. 또, 문제를 해결하여도 check문 때문에 여전히 프로그램의 전체 오더는 O(L^2)인 것 같네요. 자세히 안봐서 확실힌 모르겠지만.. 문제에서 주어지는 스트링의 크기가 1만이기 때문에 제곱 오더로는 통과가 힘들 수 있을 것 같습니다.


    11년 전 link
  • Being
    Being

    이 프로그램이 다 도는 데 1시간 걸릴 지 10년이 걸릴 지 모르니 답이 맞다고 할 순 없지요..ㅎㅎ


    11년 전 link
  • yoons
    yoons

    http://programmer.97things.oreilly.com/wiki/index.php/Use_the_Right_Algorithm_and_Data_Structure
    여기 참조 하시면 되겠네요.
    (출처 : http://www.algospot.com/wiki/read/%EC%9E%90%EC%A3%BC_%ED%95%98%EB%8A%94_%EC%8B%A4%EC%88%98_%EB%AA%A8%EC%9D%8C )


    11년 전 link
  • Being
    Being

    지금 문제에 별 상관은 없습니다만 strlen()을 직접 구현하신 이유가 있나요?


    11년 전 link
  • Being
    Being

    코드를 간략히 살펴 보니 check() 안에서 또 another를 호출하는데, 이 과정에서 O(L2)보다 크게, 자세히는 살펴보지 않았지만 O(L3)이 아닌가 싶은 아주 많은 반복을 하게 될 것 같네요. 직접 큰 입력을 만들어 넣어 보시면 도움이 될 것 같습니다.


    11년 전 link
  • chawoo77
    chawoo77

    답변감사드립니다.
    그렇군요. 맞는지도 모르는군요.
    혹시 실행시간을 제 컴퓨터에서 알 수 있는 방법은 없을까요?;;
    strlen는 제가 아직 C언어를 공부하다가 c++을 공부한지 얼마 되지 않아 iostream이 strlen을 포함하고 있는지 의문에 직접구현을 했어요
    다시 고쳐보고 한번더 도전해 봐야겠네요.ㅠ
    감사합니다.


    11년 전 link
  • Being
    Being

    실제 채점에 사용되는 데이터는 비공개입니다만, 이 경우는 직접 아주 큰 입력을 만들어 넣어 보시면 대충 감을 잡으실 것 같습니다. 이 문제를 가장 바람직하게 해결했다면 문제에서 허용하는 아무리 큰 입력이라도 매우 적은 눈 깜짝할 시간 안에 해결되어야 하겠지만, 느리건 빠르건 1초 컷 이내에만 들어오면 정답입니다 :)


    11년 전 link
  • chawoo77
    chawoo77

    아 맞췄습니다.
    strlen쓰지 않고 이스케이프문자로 판단하니까 훨씬 빠르군요.
    게대가 another함수를 시작할때마다 검사하지 않고 특정때에
    검사시키도록 순서를 조금 바꾸니까 속도가 나오네요.
    500ms로 통과했습니다~!
    감사합니다. 뭔가 속이 후련하네요.


    11년 전 link

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