MAXTACK 을 계속 풀고 있는데 아무리 해도 오답이 나와서 도움요청드립니다.

  • rapguy
    rapguy

    안녕하세요~ MAXTACK 문제를 계속 풀고 있는데 각종 예제들을 만들어서 검증을 하면
    원하는대로 답이 나오지만, SUBMIT 만 하면 오답이 나와서 검토요청 드립니다.

    예제입력은,

    6

    6
    push
    negate
    push
    subtract
    push
    add
    4294967295 1000 3

    --> 4294968298
    --> 3 1000 4294967295

    8
    push
    push
    add
    push
    subtract
    negate
    push
    add
    5 3 2 10

    --> 16
    --> 3 5 2 10

    16
    push
    push
    add
    push
    push
    subtract
    push
    push
    add
    push
    push
    subtract
    add
    subtract
    negate
    add
    8 7 6 5 4 3 2 1

    --> 16
    --> 5 6 1 7 2 3 8 4

    6
    push
    push
    subtract
    push
    subtract
    negate
    1 2 3

    --> 0
    --> 1 3 2

    22
    push
    push
    add
    push
    add
    push
    add
    push
    add
    push
    add
    push
    add
    push
    add
    push
    add
    push
    push
    add
    negate
    add
    1 2 3 4 5 6 7 8 9 10 11

    --> 60
    --> 3 4 5 6 7 8 9 10 11 1 2

    12
    push
    push
    subtract
    push
    push
    subtract
    push
    push
    subtract
    add
    add
    negate
    1 2 3 4 5 6

    --> 9
    --> 4 1 5 2 6 3

    과 같이 예제들과 지인들이 풀어서 pass 했을때 만든 예제들을 모두 넣어서 돌려보면 결과가 잘 나와서, 도데체 어디가 잘못된 것인지 모르겠습니다.

    알고리즘 자체는 p, a, s, n 의 입력에 따라 입력될 숫자들이 어떠한 부호를 갖게 될지 부호값을 계산하여
    예를들면

    arr0(-), arr1(+), arr2(+), arr3(-) 와 같이 된다면
    입력받은 숫자를 소팅해서 제일 적은 수부터 (-)부호가 들어가야 하는 곳에 넣어주고 남은 숫자들을 (+)부호가 들어가야 하는 곳에 넣어주었습니다.

    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    typedef long long int s64;
    struct maxtack
    {
        s64 val;
        bool sign; // 0 - plus, 1 - minus
    };
    
    int T, I, num_operand, input_index;
    char inst[15];
    s64 input[1000], sum;
    maxtack output[1000];
    
    void swap(int idx1, int idx2);
    int partition(int left, int right);
    void qsort(int left, int right);
    
    int main()
    {
        int index;
        scanf("%d", &T);
        while(T--)
        {
            num_operand = 0;
            sum = 0;
            vector<vector<int>> operators;
            scanf("%d", &I);
            for(int i = 0; i < I; i++)
            {
                scanf("%s", inst);
                switch(inst[0])
                {
                    case 'p':
                    {
                        vector<int> op;
                        op.push_back(++num_operand);
                        operators.push_back(op);
                    }
                        break;
                    case 'a':
                    {
                        vector<int> op1, op2;
                        op1 = operators.back();
                        operators.pop_back();
                        op2 = operators.back();
                        operators.pop_back();
                        for(vector<int>::size_type i = 0; i < op1.size(); i++) op2.push_back(op1[i]);
                        operators.push_back(op2);
                    }
                        break;
                    case 's':
                    {
                        vector<int> op1, op2; // op1 - op2
                        op1 = operators.back();
                        operators.pop_back();
                        op2 = operators.back();
                        operators.pop_back();
                        for(vector<int>::size_type i = 0; i < op2.size(); i++)
                        {
                            op2[i] = -op2[i];
                            op1.push_back(op2[i]);
                        }
                        operators.push_back(op1);
                    }
                        break;
                    case 'n':
                    {
                        vector<int> op = operators.back();
                        operators.pop_back();
                        for(vector<int>::size_type i = 0; i < op.size(); i++) op[i] = -op[i];
                        operators.push_back(op);
                    }
                        break;
                }
            }
                vector<int> op = operators.back();
                for(vector<int>::size_type i = 0; i < op.size(); i++)
                {
                    index = (op[i] > 0) ? op[i] - 1 : -op[i] - 1;
                    output[index].sign = (op[i] > 0) ? false : true;
                }
                for(int i = 0; i < num_operand; i++) scanf("%lld", &input[i]);
                input_index = num_operand - 1;
                qsort(0, input_index);
                for(int i = 0; i < num_operand; i++) if(output[i].sign) output[i].val = input[input_index--];
                for(int i = 0; i < num_operand; i++) if(!output[i].sign) output[i].val = input[input_index--];
                for(int i = 0; i < num_operand; i++)
                {
                    if(!output[i].sign) sum += output[i].val;
                    else sum -= output[i].val;
                }
                printf("%lld\n", sum);
                for(int i = 0; i < num_operand; i++) printf("%lld ", output[i].val);
                printf("\b\n");
        }
        return 0;
    }
    
    
    //====== 아래는 소팅 알고리즘으로 내림차순으로 소팅함.
    void swap(int idx1, int idx2)
    {
        s64 temp = input[idx1];
        input[idx1] = input[idx2];
        input[idx2] = temp;
    }
    
    int partition(int left, int right)
    {
        s64 pivot = input[left];
        int low = left + 1;
        int high = right;
        while(low <= high)
        {
            while(pivot <= input[low] && low <= right) low++;
            while(pivot >= input[high] && high >= left + 1) high--;
            if(low <= high) swap(low, high);
        }
        swap(left, high);
        return high;
    }
    
    void qsort(int left, int right)
    {
        if(left <= right)
        {
            int pivot = partition(left, right);
            qsort(left, pivot - 1);
            qsort(pivot + 1, right);
        }
    }
    

    5년 전
6개의 댓글이 있습니다.
  • 일루
    일루

    qsort로 호출되는 소트 부분이 이상한 것 같습니다. 그 뒷 부분은 체크 안해봤습니다만...

    사실 소트 부분은 직접 코딩 안하시고 sort(input, input + num_operand) 로 하셔도 되긴 합니다. 이 부분은 일단 Accept 받으시고 고쳐보시는 것이..


    5년 전 link
  • Stun
    Stun

    제가 확인을 좀 해봤는데.. 마지막에

    printf("\b\n") 이부분에서.. \b 이거 제거 하시고..
    그리고 리스트 출력할때 마지막 리스트 뒤에 공백 찍히는거 제거하고
    제출하니까 억셉나오네요;


    5년 전 link
  • rapguy
    rapguy

    TT Stun 님말씀이 맞네요..TT

    다 풀어놓고 마지막에 한칸씩 공백넣고 출력하는것 잘못해서 삽질했습니다. 아직 이해가 안가긴 합니다만...

    제 생각에는 1_2_3_4 (여기서 _ 는 스페이스를 의미)
    를 보여줄때

    for(int i = 0; i < 4; i++)
    {
      printf("%d ", i+1);
    }
    printf("\b");
    

    하면 될줄 알았고 실제로 제 PC에서 동작하는데 그게 아닌가봐요..


    5년 전 link
  • Being
    Being

    저렇게 하면 터미널 외의 환경에서도 잘 동작하나요? 저도 써 본 적이 없어서 어떤가요?


    5년 전 link
  • rapguy
    rapguy

    제가 터미널에서만 해봐서 괜찮아 보였던 것 같습니다. 이에 이런 printf("/b") 같은건 쓰지 말아야 할듯 합니다.


    5년 전 link
  • Being
    Being

    네. 확인해 본 것은 아니라 조심스럽지만, 제가 알기에는 실제로 \b 같은 문자를 printf()같은 출력 레이어에서 별도로 처리하는 것이 아니라 그냥 출력해내고 터미널에서 그 문자를 해석하여 \n이면 줄을 바꾸고 \a면 비프를 출력하는 등 처리를 수행합니다. 다시 말해 출력 바이트 스트림 자체는 저런 문자들을 전부 포함하고 있습니다.


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