MAXTACK 을 계속 풀고 있는데 아무리 해도 오답이 나와서 도움요청드립니다. 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); } } 10년 전
6개의 댓글이 있습니다. 일루 qsort로 호출되는 소트 부분이 이상한 것 같습니다. 그 뒷 부분은 체크 안해봤습니다만... 사실 소트 부분은 직접 코딩 안하시고 sort(input, input + num_operand) 로 하셔도 되긴 합니다. 이 부분은 일단 Accept 받으시고 고쳐보시는 것이.. 10년 전 link Stun 제가 확인을 좀 해봤는데.. 마지막에 printf("\b\n") 이부분에서.. \b 이거 제거 하시고.. 그리고 리스트 출력할때 마지막 리스트 뒤에 공백 찍히는거 제거하고 제출하니까 억셉나오네요; 10년 전 link rapguy TT Stun 님말씀이 맞네요..TT 다 풀어놓고 마지막에 한칸씩 공백넣고 출력하는것 잘못해서 삽질했습니다. 아직 이해가 안가긴 합니다만... 제 생각에는 1_2_3_4 (여기서 _ 는 스페이스를 의미) 를 보여줄때 for(int i = 0; i < 4; i++) { printf("%d ", i+1); } printf("\b"); 하면 될줄 알았고 실제로 제 PC에서 동작하는데 그게 아닌가봐요.. 10년 전 link Being 저렇게 하면 터미널 외의 환경에서도 잘 동작하나요? 저도 써 본 적이 없어서 어떤가요? 10년 전 link rapguy 제가 터미널에서만 해봐서 괜찮아 보였던 것 같습니다. 이에 이런 printf("/b") 같은건 쓰지 말아야 할듯 합니다. 10년 전 link Being 네. 확인해 본 것은 아니라 조심스럽지만, 제가 알기에는 실제로 \b 같은 문자를 printf()같은 출력 레이어에서 별도로 처리하는 것이 아니라 그냥 출력해내고 터미널에서 그 문자를 해석하여 \n이면 줄을 바꾸고 \a면 비프를 출력하는 등 처리를 수행합니다. 다시 말해 출력 바이트 스트림 자체는 저런 문자들을 전부 포함하고 있습니다. 10년 전 link 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
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(-) 와 같이 된다면
입력받은 숫자를 소팅해서 제일 적은 수부터 (-)부호가 들어가야 하는 곳에 넣어주고 남은 숫자들을 (+)부호가 들어가야 하는 곳에 넣어주었습니다.
10년 전