[백준] 10866. 덱

: solved.ac class 2 - silver 4

https://www.acmicpc.net/problem/10866

10866번: 덱

예제 입력 1

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

 

예제 출력 1

2
1
2
0
2
1
-1
0
1
-1
0
3

 

 

예제 입력 2

22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back

 

예제 출력 2

-1
-1
-1
-1
1
1
2
2
333
10
10
333
20
1234
1234
20

 

 

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct NODE { 
	int value; 
	struct NODE* before; 
	struct NODE* after; 
}node; 

void makeNode(node** p) { 
	(*p) = (node*)malloc(sizeof(node)); 
	(*p)->before = NULL; 
	(*p)->after = NULL; 
}

void push_front(node* S, int x) {
	node* p = NULL; 
	makeNode(&p); 
	p->value = x; 

	node* q = S; 
	while (q->after != NULL) q = q->after;

	p->before = q; 
	q->after = p; 
}


void push_back(node* S, int x) {
	node* p = NULL; 
	makeNode(&p); 
	p->value = x; 

	p->after = S->after; 
	p->before = S; 
	if (S->after != NULL) S->after->before = p;

	S->after = p;
}


int pop_front(node* S) {
	if (S->after == NULL) return -1; 

	node* p = S; 
	while (p->after != NULL) p = p->after;

	int data = p->value; 

	p = p->before; 
	free(p->after); 
	p->after = NULL; 
	
	return data; 
}

int pop_back(node* S) {
	if (S->after == NULL) return -1;
	node* p = S->after; 

	int data = p->value;

	S->after = p->after; 
	if (p->after != NULL) p->after->before = S;
	free(p); 

	return data;
}

int empty(node* S){
	if (S->after == NULL) return 1; 
	return 0; 
}

int front(node* S) {
	if (S->after == NULL) return -1;
	node* p = S; 
	while (p->after != NULL) p = p->after;
	return p->value; 
}

int back(node* S) {
	if (S->after == NULL) return -1; 
	else return S->after->value;
}

int main() {
	int n, x, a;
	int size = 0;
	char cmd[15] = { '\0' };

	node* S = NULL;
	makeNode(&S);
	

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%s", cmd);

		if (strcmp(cmd, "push_front") == 0) {
			scanf("%d", &x);
			push_front(S, x);
			size++;
		}
		else if (strcmp(cmd, "push_back") == 0) {
			scanf("%d", &x);
			push_back(S, x);
			size++;
		}
		else if (strcmp(cmd, "pop_front") == 0) {
			a = pop_front(S);
			printf("%d\n", a);
			if (a != -1) size--;
		}
		else if (strcmp(cmd, "pop_back") == 0) {
			a = pop_back(S);
			printf("%d\n", a);
			if (a != -1) size--;
		}
		else if (strcmp(cmd, "size") == 0) {
			printf("%d\n", size);
		}
		else if (strcmp(cmd, "empty") == 0) {
			a = empty(S);
			printf("%d\n", a);
		}
		else if (strcmp(cmd, "front") == 0) {
			a = front(S);
			printf("%d\n", a);
		}
		else if (strcmp(cmd, "back") == 0) {
			a = back(S);
			printf("%d\n", a);
		}
	}

	return 0;
}

---

해설

 

 

1. 위의 '노드' 는 구조체를 통해 구현한다.

1. 다음 노드를 가리키는 포인터 after
2. 이전 노드를 가리키는 포인터 before
3. 실제 정수값을 저장할 변수 value

이렇게 세 가지 필드로 구성해 주었다.

새 노드를 생성할 때는 먼저 그 노드를 가리킬 포인터(노드의 이름표처럼 작용할 것이다)를 만들고

노드가 들어갈 메모리 공간을 할당해준 뒤에, 포인터가 가리키는 노드의 앞/뒤 포인터를 NULL로 초기화해 준다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node { //이중 연결 리스트의 노드 구조 정의
	struct node* after; //뒤의 노드를 가리키는 포인터
	struct node* before; //앞의 노드를 가리키는 포인터
	int value; //실제 값이 들어갈 자리
}node;

void makeNode(node** p) { //새 노드 생성
	(*p) = (node*)malloc(sizeof(node)); //공간 할당
	(*p)->after = NULL; //포인터가 가리키는 노드의
	(*p)->before = NULL; //앞뒤 포인터를 NULL로 지정
}

 

2. main 함수 부분이다.

먼저 모든 노드의 시작 부분이 될 노드 S를 생성해 준다. 자료가 담기지 않은 빈 덱을 만들었다고 생각하면 된다.

이 노드 S는 실제로 값을 담고 있지 않고, 이 노드의 다음 노드부터가 실제 자료가 담긴 노드가 된다.

나중에 연결 리스트에서 포인터를 타고 탐색하거나 맨 첫/마지막 노드를 찾는 등의 작업에 S가 요긴하게 쓰일 것이다.

 

명령문의 갯수 n, push할 정수를 담을 x, 함수로 명령을 처리한 뒤 리턴되는 값을 받을 a를 선언해 주고

명령문을 담을 문자 배열 cmd도 초기화한다.

명령은 for문을 통해 받는다. 입력은 반드시 scanf를 쓰자.

push 명령을 사용할 때 명령어와 push할 정수는 공백으로 구분되어 들어오기 때문에, 공백이 입력된 곳까지 한 문장으로 인식하는 scanf를 써야 한다. (괜히 gets 썼다가 push가 안 돼서 채점도 못 받고 틀리는 수가 있다. 내가 그랬다.)

 

명령문의 인식은 string.h 헤더파일의 strcmp 함수로 한다.

두 문자열이 같으면 0을 반환하므로 이에 맞추어 코드를 작성한다.

int main() {

	node* S = NULL;
	makeNode(&S); //시작 노드 S 생성

	int n, x, a;
	int size = 0;
	char cmd[15] = { '\0' };

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%s", cmd);

		if (strcmp(cmd, "push_front") == 0) {
			scanf("%d", &x);
			push_front(S, x);
			size++;
		}
		else if (strcmp(cmd, "push_back") == 0) {
			scanf("%d", &x);
			push_back(S, x);
			size++;
		}
		else if (strcmp(cmd, "pop_front") == 0) {
			a = pop_front(S);
			printf("%d\n", a);
			if (a != -1) size--;
		}
		else if (strcmp(cmd, "pop_back") == 0) {
			a = pop_back(S);
			printf("%d\n", a);
			if (a != -1) size--;
		}
		else if (strcmp(cmd, "size") == 0) {
			printf("%d\n", size);
		}
		else if (strcmp(cmd, "empty") == 0) {
			a = empty(S);
			printf("%d\n", a);
		}
		else if (strcmp(cmd, "front") == 0) {
			a = front(S);
			printf("%d\n", a);
		}
		else if (strcmp(cmd, "back") == 0) {
			a = back(S);
			printf("%d\n", a);
		}
	}

	return 0;
}

 

 

3. push 연산들이다. 원리는 위에서 이미지로 설명했으므로 참고해 주기 바란다.

공통적으로 노드를 생성한 뒤, value에 자료를 저장하고

push_front의 경우에는 S에서부터 시작해 맨 끝 노드까지 이동하여 그 끝에 새 노드를 달아주고,

push_back의 경우에는 S와 그 다음 노드 사이에 새 노드를 끼워넣어주면 된다.

//정수 X를 덱의 앞에 넣는다.
void push_front(node* S, int x) {
	node* p = NULL; //포인터 생성
	makeNode(&p); //노드 생성
	p->value = x; //자료 저장

	node* q = S; //인자로 받아온 노드를 가지고
	while (q->after != NULL) q = q->after;
	//다음 노드가 없을 때까지 앞으로 이동
	p->before = q; //새 노드의 before은 기존 노드의 after에
	q->after = p; //기존 노드의 after은 새 노드의 before에 연결
}

//정수 X를 덱의 뒤에 넣는다.
void push_back(node* S, int x) {
	node* p = NULL; //포인터 생성
	makeNode(&p); //노드 생성
	p->value = x; //자료 저장

	p->after = S->after; //새 노드의 after은 시작 노드의 after로,
	p->before = S; //before은 시작 노드로
	if (S->after != NULL) S->after->before = p;
	//만약 시작 노드 앞에 기존 노드가 있다면
	//그 기존 노드의 before을 새 노드에 연결
	S->after = p;
	//시작 노드는 after로 새 노드를 가리키도록 지정
}

 

4. pop 연산들이다. 연결 리스트에서 노드의 삭제는 간단하다.

pop_front의 경우 맨 끝에 달려 있는 노드이므로 그 이전 노드와의 연결을 끊고, 삭제할 노드의 공간을 해제한다.

pop_back의 경우 앞뒤에 달려 있는 노드들을 서로 연결해 주고, 연결에서 제외된 해당 노드의 공간을 해제한다.

이 과정 중간에 pop할 노드에 들어 있던 value값을 따로 담아 두었다가

노드 삭제가 끝나면 return해 주면 pop 연산이 된다.

//덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다.
//만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
int pop_front(node* S) {
	if (S->after == NULL) return -1; //덱이 빈 경우 처리

	node* p = S; //포인터 p에 시작 노드를 달아주고
	while (p->after != NULL) p = p->after;
	//다음 노드가 없을 때까지 after 포인터를 타고 이동

	int data = p->value; 
	//p 포인터가 멈춘 노드에 들어있는 정수값 추출

	p = p->before; //그전 노드로 이동해서
	free(p->after); //가장 앞의 노드에 할당된 공간을 해제
	p->after = NULL; //그 노드를 가리키던 포인터를 비움
	
	return data; //빼두었던 정수값 출력
}

//덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다.
//만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
int pop_back(node* S) {
	if (S->after == NULL) return -1;//덱이 빈 경우 처리

	node* p = S->after; //시작 노드의 바로 다음 노드를 포인터 p에 지정

	int data = p->value;
	//해당 노드에 들어있는 정수값 추출
	S->after = p->after; //가장 뒤에 있는 노드의 그다음 노드를 S에 연결

	if (p->after != NULL) p->after->before = S;
	//만약 가장 뒤의 노드에 다음 노드가 존재한다면
	//그 노드의 before도 S에 연결

	free(p); //p로 잡고 있던 노드의 공간 해제

	return data; //빼두었던 정수값 출력
}

 

5. empty, front, back 연산들이다.

 

empty의 경우 덱이 비었는지 (push된 노드가 없는지)를 확인하는 명령이므로,

시작 노드 S의 after에 노드가 하나라도 달려 있는지를 확인해 주면 된다. 없으면 NULL 값이 있을 것이다.

 

front는 포인터 하나를 생성해 노드 S에서부터 after 방향으로 계속 이동해 나간다. S의 after에 노드 1번, 노드 1번의 after에 노드 2번, 노드 2번에... ... 이런 식으로 연결되어 있을 것이다. 그렇게 가다가 after 포인터에 NULL 값이 들어있는 노드가 있다면 그 노드가 front다. 들어있는 정수값을 출력해주면 된다.

 

back은 더욱 간단하다. S 바로 다음에 연결된 노드가 back이다. 마찬가지로 들어있는 정수값을 출력해주면 된다.

int empty(node* S){
	if (S->after == NULL) return 1; //덱이 비었을 경우 처리
	//시작 노드에 연결된 노드가 없으면 1 출력
	else return 0; //아니라면 0 출력
}

int front(node* S) {
	if (S->after == NULL) return -1; //덱이 비었을 경우 처리
	node* p = S; //시작 노드에 포인터를 달고
	while (p->after != NULL) p = p->after;
	//다음 노드가 없을 때까지 after 방향으로 이동
	return p->value; //멈춘 노드에 저장된 정수값 출력
}

int back(node* S) {
	if (S->after == NULL) return -1; //덱이 비었을 경우 처리
	else return S->after->value;
	//덱이 비어있지 않다면 시작 노드의 바로 다음 노드에 저장된 값 출력
}