글 읽기 - 덱 사이즈에 따라 맞고 틀리는게 달라지는데 왜 그럴까요?

giyobe 6년 전 0

덱 사이즈를 줄이면 시간초과가 뜨다가 사이즈를 1000 정도로 크게 키우면 0ms로 맞았습니다가 뜹니다.

N은 50보다 작거나 같기 때문에 배열 사이즈가 55정도만 되어도 제대로 동작해야 하는데 말입니다.

어디가 잘못된 것일까요?

구현은 다음과 같은 방식으로 하였습니다.

1) dq 배열에 1부터 N까지 숫자를 앞에서부터 차례대로 enqueue

2) 1부터 M까지 숫자 중 찾아야 할 숫자가 들어있는 인덱스를 n에 저장

3) n - front와 rear - n을 비교하여 작은 방향으로 shift 및 shift 횟수를 저장 및 shift 후 목표 숫자 제거

4) 2)와 3)을 반복

5) 누적된 shift 횟수를 출력

#include <stdio.h>
#define DQ_SIZE 1000
#define CAL_IDX(X) ((X) > 0 ? ((X) % DQ_SIZE) : ((X + DQ_SIZE) % DQ_SIZE))

int dq[DQ_SIZE];
int front, rear, shiftCnt;

//op1
int removeFirst(void)
{
	int temp = dq[CAL_IDX(front)];
	dq[CAL_IDX(front)] = 0;
	front++;
	return temp;
}

//op2
void shiftLeft(int rep)
{
	shiftCnt += rep;
	while (rep--) {
		dq[CAL_IDX(rear)] = dq[CAL_IDX(front)];
		rear++;
		dq[CAL_IDX(front)] = 0;
		front++;
	}
}

//op3
void shiftRight(int rep)
{
	shiftCnt += rep;
	while (rep--) {
		front--;
		rear--;
		dq[CAL_IDX(front)] = dq[CAL_IDX(rear)];
		dq[CAL_IDX(rear)] = 0;
	}
}

int main(void)
{
	int N, M, n;
	scanf("%d %d", &N, &M);

	for (int i = 0; i < N; i++)
		dq[rear++] = i + 1;

	for (int i = 0; i < M; i++) {
		scanf("%d", &n);
		for (int j = CAL_IDX(front); CAL_IDX(j) != CAL_IDX(rear); j++) {
			if (dq[CAL_IDX(j)] == n) {
				n = j;
				break;
			}
		} // n은 이번에 뽑아야 할 idx

		if (CAL_IDX(n - front) <= CAL_IDX(rear - n)) {
			shiftLeft(CAL_IDX(n - front));
			removeFirst();
		}
		else {
			shiftRight(CAL_IDX(rear - n));
			removeFirst();
		}
	}

	printf("%d", shiftCnt);

	return 0;
}

giyobe 6년 전 0

line 59, 63에서 음수가 전달되는 것이 문제였던 듯 합니다.

line 3를 아래와 같이 수정하니 제대로 동작하는군요.

나름 음수 처리를 한다고 해놨는데 앞으로는 확실히 해야겠네요.

1) C언어 모듈로 연산자는 X % Y 에서 X의 부호(+ 또는 -)에 따라 결과가 출력됨

2) 그냥 큰 양수로 만들어놓자...

// #define CAL_IDX(X) ((X) > 0 ? ((X) % DQ_SIZE) : ((X + DQ_SIZE) % DQ_SIZE))
#define CAL_IDX(X) ((X) > 0 ? ((X) % DQ_SIZE) : ((X + (DQ_SIZE * 10000)) % DQ_SIZE))

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

문제

문제

출처

ICPC

덱 사이즈에 따라 맞고 틀리는게 달라지는데 왜 그럴까요?

giyobe 6년 전 0

giyobe 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말