유의사항
•
전역 변수 금지
•
첫 번째 인수는 스택의 맨 위에 있어야 한다.
•
제공된 바이너리와 똑같은 동작을 재현할 필요는 없다.
오류 관리는 필수지만 인수를 구문 분석하는 방법을 결정하는 것은 사용자에게 달려 있다.
구현 순서
필요 조건
•
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개의 스택 a 및 b 가 존재한다.
•
첫번째 요소와 마지막 요소에 대한 삽입/삭제가 용이해야 하므로, 자료구조는 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
복사
테스트 프로그램
•
전체 테스트
git clone https://github.com/Arkhavy/Arktest_Push_Swap.git
cd Arktest_Push_Swap
./arktest.sh
Shell
복사
•
비쥬얼 테스트
$ ARG="$(seq 500 | sort -R)"
$ echo $ARG | pbcopy # 카피한 내용을 첫번째 입력창에 복사 (매개변수)
$ ./push_swap $ARG | pbcopy # 카피한 내용을 두번째 입력창에 복사 (실행 명령어)
# Start 누르면 시작!
Shell
복사
