QUADTREE에서 어떤 부분에서 예외처리, 오답이 발생하는지 모르겠습니다.

  • PuzzleLeaf
    PuzzleLeaf
    #include<iostream>
    #include<list>
    using namespace std;
    
    // 나중에 수정
    void reset(char *text)
    {
        for (int i = 0; i < 1000; i++)
            text[i] = ' ';
    }
    // 나중에 수정
    int checkText(char *text)
    {
        for (int i = 0; i < 1000; i++)
        {
            if (text[i] == ' ')
                return i;
        }
        return 1000;
    }
    //리스트의 마지막 값을 리턴
    list<char>::iterator checkEnd(list<char> &text)
    {
        list<char>::iterator iter = text.end();
        --iter; // end는 NULL이므로
        return iter;
    }
    list<char>::iterator reverseText(list<char> &text,list<char>::iterator start, list<char>::iterator end)
    {
        list<char>::iterator *t = new list<char>::iterator[4];
    
        if (*text.begin()!='x')
            return end;
    
        //맨 처음이 x인 경우
        for (int i = 0; i < 4; i++)
        {
            ++end;
            t[i] = end;
            if (*end == 'x')
            {
                end = reverseText(text, start, end);
    
            }
        }
    
        //4개가 모두 x가 아닐때
        if (end != checkEnd(text) && *t[3] !='x')
        {
            ++t[3];
            text.insert(t[0], t[2], t[3]);
            end = text.erase(t[2], t[3]);
            --end;
    
        }
        //맨 끝이 x인 경우
        else if (end != checkEnd(text) && *t[3] == 'x')
        {
            end = t[3];
            for (int i = 0; i < 4; i++)
            {
                ++end;
                if (*end == 'x')
                    i -= 4;
            }
            ++end;
            text.insert(t[0], t[2], end);
            end = text.erase(t[2], end);
            --end;
        }
        //마지막 값인 경우
        else if (end == checkEnd(text))
        {
            end = text.end();
            text.insert(t[0], t[2], end);
            text.erase(t[2], end);
            delete[] t;
            return text.begin();
        }
    
        delete[] t;
        return end;
    
    
    }
    
    int main()
    {
        int count = 0;
        int t = 0;
        char *text;
    
        cin >> count;
    
        for (int i = 0; i < count; i++)
        {
            text = new char[1000];
            list<char> tex;
            list<char>::iterator iter;
            reset(text);
    
            cin >> text;
            t = checkText(text);
            for (int i = 0; i<t; i++)
                tex.push_back(text[i]);
    
            reverseText(tex, tex.begin(), tex.begin());
    
            for (iter = tex.begin(); iter != tex.end(); iter++)
                cout << *iter;
            cout << endl;
    
            delete[]text;
    
    
        }
        return 0;
    
    }
    

    QUADTREE 문제를 리스트를 이용하여 풀었습니다. char 배열을 이용해서 각 배열바다 값을 하나씩 받고 이 값들을 list에 넣어 주었습니다.

    그리고 reverseText 함수를 이용하여 x 1 2 3 4 가 입력이 되면 리스트에서 1번 위치에 3 4의 값을 삽입하고 3 4를 지워서 x 3 4 1 2 가 되도록 하는 원리로 함수를 작성했습니다.

    각 호출되는 함수당 최대 4번 재귀함수를 호출하고 각 함수에서 iterator 배열이 존재하여 위에서 x 1 2 3 4 에서 각 1 2 3 4의 위치를 나타내게 하였습니다.

    end iterator가 문자열의 끝에 도달하기 전에는 각 만나는 x에서
    x 3 4 1 2로 위치를 바꾸고

    x가 4번째 위치에 있을 때 따로 예외를 처리하여 x 3 4 1 2 가 되도록 했고 end iterator를 이용하여 입력한 문자열의 마지막에 도달했을 경우 전체의 문자열에서 x 3 4 1 2 가 되도록 했습니다.

    나름 여러가지 예제를 그려보면서 입력해봤는데 오류가 나는 케이스를 아직 발견하지 못했습니다.


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

    문자열이 1000이하면 배열을 1001까지 잡고 reset, check 도 i=0 ; i <= 1000 까지 해야겠죠?


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