unhak96   5년 전

10866번 덱문제 결과값 잘 나오는데 틀렸다고 나오네요. 어디가 문제인지 모르겠네요.

#include <stdio.h>
#include <string.h>

typedef struct _queue
{
    int a[10001];
    int size;
    int cnt;
    int front,back;
}Queue;

int main(void)
{
    int i;
    char a[11];
    int n;
    int temp;
    Queue que;
    que.size=1;
    que.front=1;
    que.back=1;
    que.cnt=0;

    scanf("%d",&n);
    que.size=n+1;
    for(i=0;i<n;i++)
    {        
        scanf("%s",a);
        if(strcmp(a,"push_front")==0)
        {
             scanf("%d",&temp);
             que.front=(que.front-1)%que.size;
             que.a[que.front]=temp;
             que.cnt++;

        }
        else if(strcmp(a,"push_back")==0)
        {
             scanf("%d",&temp);
             que.a[que.back]=temp;
             que.back=(que.back+1)%que.size;
             que.cnt++;
        }
        else if(strcmp(a,"pop_front")==0)
        {
           if(que.cnt==0)
            {
                printf("-1\n");
            }
            else
            {
                printf("%d\n",que.a[que.front]);
                que.front=(que.front+1)%que.size;
                que.cnt--;
            }

        }
        else if(strcmp(a,"pop_back")==0)
        {
            if(que.cnt==0)
            {
                printf("-1\n");
            }
            else
            {
                printf("%d\n",que.a[que.back-1]);
                que.back=(que.back-1)%que.size;
                que.cnt--;
            }
        }
        else if(strcmp(a,"size")==0)
        {
            printf("%d\n",que.cnt);

        }
        else if(strcmp(a,"empty")==0)
        {
            if(que.cnt==0)
            {
                printf("1\n");
            }
            else
            {
                printf("0\n");
            }
        }
        else if(strcmp(a,"front")==0)
        {
            if(que.cnt==0)
            {
                printf("-1\n");
            }
            else
            {
                printf("%d\n",que.a[que.front]);
            }
        }
        else if(strcmp(a,"back")==0)
        {
            if(que.cnt==0)
            {
                printf("-1\n");
            }
            else
            {
                printf("%d\n",que.a[que.back-1]);
            }
        }
    }

    return 0;
}

djm03178   5년 전

push_front를 계속하면 인덱스가 어디로 갈까요?

unhak96   5년 전

제가 질문을 이해 못한것 같습니다만, 인덱스가 어디로 갈까요?라는 부분 설명 다시 부탁드려도 될까요?

20
push_front 1
push_front 2
push_front 3
push_front 4
push_front 5
push_front 6
push_front 7
push_front 8
push_front 9
push_front 10
push_front 11
push_front 12
push_front 13
push_front 14
push_front 15
size
15
pop_back
1
pop_back
2
back
3
size
13

djm03178   5년 전

처음에 front가 1이죠.

한 번 push_front를 하면 0이 됩니다.

한 번 더 하면 -1이 되고, 또 하면 -2, 또 하면 -3, ... 해서 할당되지 않은 곳을 계속 침범합니다.

unhak96   5년 전

네, 답변 감사드립니다.

그 부분은 아래와 같이 구현되어 있고, 테스트 결과도 문제가 없습니다. 

테스트 결과 이것 저것 해보는데 잘 안보이네요 T.T

que.size=n+1;  //명령의 수 N

que.front=(que.front-1)%que.size;

----------test결과...

20
push_front 1
push_front 2
push_front 3
push_front 4
push_front 5
push_front 6
push_front 7
push_front 8
push_front 9
push_front 10
push_front 11
push_front 12
push_front 13
push_front 14
push_front 15
size
15
pop_back
1
pop_back
2
back
3
size
13

djm03178   5년 전

적은 수만 가지고 테스트를 해보고서는 모릅니다. 메모리 할당이라는 게 그렇게 딱 그 크기만큼만 이루어지는 것이 아니거든요.

que.front가 0인 상태에서 다음이 실행되면,

que.front=(que.front-1)%que.size;

que.front-1은 -1입니다. size가 10이었다고 하면, 이게 9가 된다고 말씀하시는 거죠?

아닙니다. -1을 10으로 나눈 나머지는 -1입니다. 직접 출력을 해보세요.

djm03178   5년 전

프로그램의 동작이 완전하다는 걸 보이려면 그 과정에 결함이 없음을 보여야 하는 것이지, 단 1~20번의 테스트에서 문제가 없다고 해서 문제가 없는 코드인 건 아닙니다.

간단하게 출력만 해봐도 알 수 있고, 디버그 모드로 돌리면 마지막에 캐치까지 해줍니다.

cmd_2018-01-12_00-20-42.png

djm03178   5년 전

참고로 이러한 문제 때문에 방향을 반대로 돌아가는 경우에는 그냥 1을 빼는 것이 아니라 size를 더하고 1을 뺀 뒤에 나머지 연산을 하는 것이 안전합니다.

unhak96   5년 전

꼼꼼한 답변 감사합니다.

말씀하신 부분 아래 두개 수정해서 채첨해 봤는데  틀렸다고 나오네요. T.T

que.front=(que.front+que.size-1)%que.size;

que.back=(que.back+que.size-1)%que.size;


우선은 linked list로 구현하고 오늘은 그만하려고 합니다. 내일 다시 봐야할 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.