백준 10866(덱) c언어

문제

10866번: 덱

c++ STL을 이용하면 매우 쉽게 구할 수 있지만 C언어로 구현하면 꽤 까다로운 문제 였습니다.

C언어로 직접 코드를 다 구현해보는게 덱을 이해하는데 큰 도움이 되었습니다.

코드를 보겠습니다.

---

void push_front(int a);
void push_back(int b);
int empty();
void pop_front();
void pop_back();
int deque[10001];
int cnt = 0;
int front = 0;

먼저 들어가기에 앞서 전역변수로 설정해놓은 함수들과 배열, 변수 입니다.

변수 cnt는 덱의 뒷 부분의 인덱스를 의미하고, 변수 front는 덱의 앞 부분의 인덱스를 의미합니다.

---

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

	while (n--) {
		char ch[20];
		scanf("%s", &ch);

		if (strcmp(ch, "push_front") == 0) {
			int a;
			scanf("%d", &a);
			push_front(a);
		}
		else if (strcmp(ch, "push_back") == 0) {
			int b;
			scanf("%d", &b);
			push_back(b);
		}
		else if (strcmp(ch, "empty") == 0) {
			if (empty())
				printf("1\n");
			else printf("0\n");
		}
		else if (strcmp(ch, "pop_front") == 0) {
			if (empty())
				printf("-1\n");
			else pop_front();
		}
		else if (strcmp(ch, "pop_back") == 0) {
			if (empty())
				printf("-1\n");
			else pop_back();
		}
		else if (strcmp(ch, "front") == 0) {
			if (empty())
				printf("-1\n");
			else printf("%d\n", deque[front]);
		}
		else if (strcmp(ch, "back") == 0) {
			if (empty())
				printf("-1\n");
			else printf("%d\n", deque[cnt - 1]);
		}
		else if (strcmp(ch, "size") == 0) {
			printf("%d\n", cnt - front);
		}
	}
	return 0;
}

메인함수 전부입니다. 명령부분은 strcmp함수를 이용하여 명령을 받아주었습니다.

이제 각 함수의 코드를 보겠습니다.

---

push_front 함수

void push_front(int a) {
	for (int i = cnt; i >= front; i--) {
		if (i == 0)
			continue;
		deque[i] = deque[i - 1];
	}
	cnt++;
	deque[front] = a;
}

이번 문제에서 가장 까다로웠던 함수입니다.

예를들어 deque에 deque[0] =1, deque[1]=2가 있다고 한다면

push.front(3)을 명령하면 원래 있던 원소가 한칸씩 오른쪽으로

이동한후 맨앞에 남은 자리에 3을 삽입해 주면 됩니다.

for(int i=front; i<cnt;i++){
    deque[i+1]=deque[i];
}

이 코드는 제가 처음에 for문에서 짠 코드입니다.

단순해 보이지만 이 코드 때문에 문제를 틀렸었습니다.

저 코드로 push_front(2), push_front(1) 을 하면 그림의 배열처럼

정상적으로 들어갑니다.

하지만 세번째 원소부터 push_front(3)을 하게 되면 배열에는 3, 1, 1 이 들어가게 됩니다.

i=0) deque[1] = deque[0] =1

i=1) deque[2] = deque[1] =1

따라서 deque[0]=3, deque[1]=1, deque[2]=1 이 됩니다.

이처럼 for문이 앞에서 뒤로 옮기는 것은 중복될 수 있습니다. 그래서 앞에 원소를 먼저 옮기지 않고 맨뒤의 원소를

먼저 옮기면 중복되는 문제를 방지할 수 있습니다.

마지막에 i=0이 되면 deque[0]은 비워놔야하기 때문에 그리고 for문 안에서 deque[0]=deque[-1] 같은 오류가 발생하기 때문에 i가0이면 continue를 해서 무시해주었습니다.

나머지 함수들은 문제에서 다루어서 쉽게 구현이 가능했습니다.

---

전체 코드입니다.

#include<stdio.h>
#include<string.h>
void push_front(int a);
void push_back(int b);
int empty();
void pop_front();
void pop_back();
int deque[10001];
int cnt = 0;
int front = 0;
int main() {
	int n;
	scanf("%d", &n);

	while (n--) {
		char ch[20];
		scanf("%s", &ch);

		if (strcmp(ch, "push_front") == 0) {
			int a;
			scanf("%d", &a);
			push_front(a);
		}
		else if (strcmp(ch, "push_back") == 0) {
			int b;
			scanf("%d", &b);
			push_back(b);
		}
		else if (strcmp(ch, "empty") == 0) {
			if (empty())
				printf("1\n");
			else printf("0\n");
		}
		else if (strcmp(ch, "pop_front") == 0) {
			if (empty())
				printf("-1\n");
			else pop_front();
		}
		else if (strcmp(ch, "pop_back") == 0) {
			if (empty())
				printf("-1\n");
			else pop_back();
		}
		else if (strcmp(ch, "front") == 0) {
			if (empty())
				printf("-1\n");
			else printf("%d\n", deque[front]);
		}
		else if (strcmp(ch, "back") == 0) {
			if (empty())
				printf("-1\n");
			else printf("%d\n", deque[cnt - 1]);
		}
		else if (strcmp(ch, "size") == 0) {
			printf("%d\n", cnt - front);
		}
	}
	return 0;
}
void push_front(int a) {
	for (int i = cnt; i >= front; i--) {
		if (i == 0)
			continue;
		deque[i] = deque[i - 1];
	}
	cnt++;
	deque[front] = a;
}
void push_back(int b) {
	deque[cnt++] = b;
}
int empty() {
	if (cnt == front)
		return 1;
	else return 0;
}
void pop_front() {
	printf("%d\n", deque[front]);
	deque[front] = 0;
	front++;
}
void pop_back() {
	printf("%d\n", deque[cnt - 1]);
	deque[cnt - 1] = 0;
	cnt--;
}