Search
Duplicate
📊

[push_swap] 구현 순서 가이드

간단소개
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
42cursus
태그
Scrap
8 more properties
유의사항
전역 변수 금지
첫 번째 인수는 스택의 맨 위에 있어야 한다.
제공된 바이너리와 똑같은 동작을 재현할 필요는 없다. 오류 관리는 필수지만 인수를 구문 분석하는 방법을 결정하는 것은 사용자에게 달려 있다.

구현 순서

필요 조건

push_swap : 스택 정렬
Program name
push_swap
Turn in files
Makefile, *.h, *.c
Makefile
NAME, all, clean, fclean, re
Arguments
stack a: A list of integers
External functs.
read, write, malloc, free, exit • ft_printf and any equivalent YOU coded
Libft authorized
Yes
Description
Sort stacks
checker : 정렬 명령어 실행
Program name
checker
Turn in files
.h, *.c
Makefile
bonus
Arguments
stack a: A list of integers
External functs.
read, write, malloc, free, exit • ft_printf and any equivalent YOU coded
Libft authorized
Yes
Description
Execute the sorting instructions

공통 부분 - 구문 분석

실행파일은 INT_MIN ~ INT_MAX 범위의 중복없는 임의의 숫자를 인자로 받는다.
입력값으로 받은 첫번째 인수는 스택의 맨 위에 있어야한다.
정수가 아니거나 중복인 경우 “Error\n”을 출력한다.
$ ./push_swap 3 2 2 4 | cat -e # 중복 에러 Error$ $ ./push_swap 3 2 2147483648 | cat -e # INT 범위를 초과한 경우 Error$ $ ./push_swap 3 2 one | cat -e # 정수가 아닌 경우 Error$ $ ./push_swap "" 1 | cat -e # 정수가 아닌 경우 Error$
Shell
[참고] 두 실행파일의 main 구조

공통 부분 - 명령어

pa (push a)
b의 맨 위에 있는 첫 번째 요소를 가져와서 a의 맨 위에 놓는다. b가 비어 있으면 아무 것도 하지 않는다.
pb (push b)
a의 맨 위에 있는 첫 번째 요소를 가져와서 b의 맨 위에 놓는다. a가 비어 있으면 아무 것도 하지 않는다.
ss
sa와 sb를 동시에 사용한다.
sb (swap b)
스택 b의 맨 위에 있는 처음 2개의 요소를 교환한다. 요소가 하나만 있거나 없는 경우 아무 작업도 수행하지 않는다.
rr
ra와 rb를 동시에 사용한다.
ra (rotate a)
스택 a의 모든 요소를 1만큼 위로 이동한다. (첫 번째 요소가 마지막 요소로)
ra (rotate a)
스택 b의 모든 요소를 1만큼 위로 이동한다. (첫 번째 요소가 마지막 요소로)
rrr
rra와 rrb를 동시에 사용한다.
rra (reverse ra)
스택 a의 모든 요소를 1만큼 아래로 이동한다. (마지막 요소가 첫 번째 요소로)
rrb (reverse rb)
스택 b의 모든 요소를 1만큼 아래로 이동한다. (마지막 요소가 첫 번째 요소로)

스택 구현

2개의 스택 ab 가 존재한다.
첫번째 요소와 마지막 요소에 대한 삽입/삭제가 용이해야 하므로, 자료구조는 deque를 추천한다.
array : 인덱스 계산 필요
linked list : 마지막 요소 접근에 시간이 오래 걸림
double linked list : 간단하게 구현 가능
typedef struct s_stack t_st; struct s_stack_node { int num; // 입력된 인자값 unsigned int idx; // 입력된 전체 값에서의 순서 struct s_stack_node *prev; struct s_stack_node *next; }; struct s_stack { unsigned int cnt; // 현재 스택의 개수 struct s_stack_node *node[2]; // 노드의 시작과 끝을 저장 }; struct s_pushswap { unsigned int cnt; // 전체 스택의 사이즈 struct s_stack a; struct s_stack b; }; enum e_rear { FRONT = 0, REAR = 1 }
C

스택 조작

양방향으로 데이터를 추출하고 삽입할 수 있는 deque, enque 함수만 구현 하면 나머지는 쉽다.
struct s_stack *deque(struct s_stack *st, enum e_rear rear); void enque(struct s_stack *st, enum e_rear rear, struct s_stack_node *node);
C
int push(struct s_stack *from, struct s_stack *to) { struct s_stack_node *node; if (from->cnt < 1) return (0); // 뺄 게 없으므로 명령어 처리 X node = deque(from, FRONT); enque(to, FRONT, node); return (1); } int swap(t_stack *st) { struct s_stack_node *node[2]; if (st->cnt < 2) return (0); // swap 할 게 없으므로 명령어 처리 X node[0] = deque(st, FRONT); node[1] = deque(st, FRONT); enque(st,FRONT, node[0]); enque(st,FRONT, node[1]); return (1); } int rotate(t_stack *st, enum e_rear rear) { struct s_stack_node *node; if (st->cnt < 1) return (0); // 뺄 게 없으므로 명령어 처리 X node = deque(st, is_rear); enque(st, !rear, node); return (1); }
C

명령어 구현

int command(struct s_pushswap *ps, char *cmd) { if (ft_strncmp(cmd, "pa\n", 4) == 0) return push(&ps->a, &ps->b); if (ft_strncmp(cmd, "pb\n", 4) == 0) return push(&ps->b, &ps->a); if (ft_strncmp(cmd, "sa\n", 4) == 0) return swap(&ps->a); if (ft_strncmp(cmd, "sb\n", 4) == 0) return swap(&ps->b); if (ft_strncmp(cmd, "ss\n", 4) == 0) return swap(&ps->a) && swap(&ps->b); ... if (ft_strncmp(cmd, "rra\n", 5) == 0) return rotate(&ps->a, REAR); ... ft_putstr_fd(2, "Error\n"); // 명령어를 찾을 수 없는 경우 exit(-1); }
C

보너스 부분 - checker

명령어에 대한 검증을 하지 않고 정렬 먼저 수행하는 경우, 원인 분석이 매우 어려워진다!
따라서, 정렬을 수행하는 push_swap이 아니라 checker를 먼저 구현해야 한다!
get_next_line 함수를 사용하여 표준 입력에서 명령어를 입력받는다. (ex. “pa\n”)
모든 명령어를 읽고 나면 프로그램은 인수로 받은 스택에서 명령어를 실행한다.

입력값 검증

스택 a가 오름차순으로 정렬되고 스택 b가 비어 있으면 표준 출력에서 "OK\n"을 표시한다.
$>./checker 3 2 1 0 rra pb sa rra pa OK
Shell
다른 모든 경우에는 표준 출력에 "KO\n"를 표시한다.
$>./checker 3 2 1 0 sa rra pb KO
Shell
오류의 경우 표준 오류에 "Error\n"을 표시한다.
일부 인수는 정수가 아닌 경우
$>./checker 3 2 one 0 Error $>./checker "" 1 Error
Shell
일부 인수가 정수보다 큰 경우
$>./checker 2147483648 1 Error
C
중복이 있는 경우
$>./checker 3 2 2 1 Error
C
형식이 잘못된 경우
$>./checker 3 2 1 0 pa Error
C
명령이 존재하지 않는 경우
$>./checker 3 2 1 0 pp Error
C

명령어 검증

아래와 같이 명령어 수행 후 현재 스택 정보를 표시하는 디버깅 출력을 만들어두면 유용하다.
최소한 다음과 같은 상황에서 모든 명령어가 제대로 잘 수행 되는지에 대해 확인하고 검증해야 한다.
스택이 비어있는 경우
스택에 하나만 있는 경우
스택에 2개 이상 있는 경우
스택에 3개 이상 있는 경우
$>./checker 3 2 1 0 rra # 현재상태 : rra 0 3 2 1 / pb # 현재상태 : pb 3 2 1 / 0 sa # 현재상태 : sa 2 3 1 / 0 rra # 현재상태 : rra 1 2 3 / 0 pa # 현재상태 : pa 0 1 2 3 / OK
Shell
[참고] checker 샘플코드

필수 부분 - push_swap

스택을 오름차순으로 정렬시킨다. 이미 정렬된 경우 아무것도 출력하지 않고 그대로 종료해야 한다.

정렬 알고리즘

모래시계, 그리디, 퀵소트, 병합정렬 등의 방법이 있으므로 원하는 방법대로 구현하면 된다.

디버깅 및 간이 테스트

디버깅을 위해 현재 스택 정보를 표시하는 함수를 만들어두는 것을 권장한다
$ ./push_swap 3 2 1 4 | cat -e ra$ # ex. 2 1 4 3 / pb$ # ex. 1 4 3 / 2 pb$ # ex. 4 3 / 1 2 ss$ # ex. 3 4 / 2 1 pa$ # ex. 2 3 4 / 1 pa$ # ex. 1 2 3 4 /
Shell
다음의 명령어로 간이 테스트를 진행할 수 있다.
$ ./push_swap $(seq 100 | sort -R)
Shell
$ ARG=$(seq 500 | sort -R) $ ./push_swap $ARG | nl # 명령어 개수 확인 $ ./push_swap $ARG | ./checker $ARG # 정렬 여부 확인
Shell

테스트 프로그램

비쥬얼 테스트
$ ARG="$(seq 500 | sort -R)" $ echo $ARG | pbcopy # 카피한 내용을 첫번째 입력창에 복사 (매개변수) $ ./push_swap $ARG | pbcopy # 카피한 내용을 두번째 입력창에 복사 (실행 명령어) # Start 누르면 시작!
Shell