과제 설명
-
정수값들의 집합, 2개의 스택, 2개의 스택을 조작하기 위한 명령어 집합이 주어짐.
-
여기서 주어진 명령어를 사용하여 입력 받은 정수 인자들을 효율적으로 정렬하는 프로그램을 만드는 것.
과제 목표 or 하는 이유
-
정렬 알고리즘을 작성하는 것은 코더의 인생에서 언제나 가장 중요한 의미를 가짐.
-
효율적인 알고리즘 구상을 위해 복잡도를 고려하며 좀 더 좋은 코드가 무엇일지 생각해 볼 수 있음.
-
연결리스트와 재귀함수를 활용하며 포인터와 코드 전반적인 동작흐름을 이해할 수 있다.
과제 규칙
-
a와 b라는 이름의 두 개의 스택으로 이루어져 있다.
-
정렬은 다음과 같은 상태에서 시작한다.
- a는 서로 중복되지 않는 음수 혹은 양수인 난수들을 포함함.
- b는 비어있다.
-
목표는 스택 a에 오름차순으로 수를 정렬하는 것이다.
-
이를 위해 다음 연상들을 수행할 수 있다. (명령어 집합)
- sa(sb) [swap a(b)] : 스택 a(b)의 가장 위에 있는 두 원소의 위치를 서로 바꾼다.
- ss (sa and sb) : sa와 sb를 동시에 실행한다.
- pa(pb) [push a(b)] : 스택 b(a)에서 가장 위에 있는 원소를 가져와서 스택 a(b)의 맨 위에 넣는다. 스택 b(a)가 비어 있으면 아무 것도 하지 않는다.
- ra(rb) [rotate a(b)] : 스택 a(b)의 모든 원소들을 위로 1 index만큼 올린다. -> 맨 위에 원소가 맨 밑으로 이동
- rr (ra and rb) : ra와 rb를 동시에 실행한다.
- rra(b) [reverse rotate a(b)] : 스택 a(b)의 모든 원소들을 아래로 1 index만큼 내린다. -> 맨 밑 원소가 맨 위로 이동.
- rrr (rra and rrb) : rra와 rrb를 동시에 실행한다.
-
push_swap이라는 이름의 프로그램을 작성해야 한다.
- 이 프로그램은 스택 a에 들어갈 값들을 정수 리스트의 형태로 포맷팅하여 인자로 받는다.
- 첫 번째 인자는 스택의 탑이 된다.
ex) 입력으로 1 2 3 4 5가 들어오면 1이 스택의 탑, 5가 바텀임. - 명령어들은 '\n'(개행)으로만 구분되어야 한다.
- 프로그램의 목표는 가능한 적은 개수의 명령어 집합으로 스택을 정렬하는 것. (평가내용 중 프로그램에서 도출한 명령어의 수와 허용된 최대 작업수를 비교하는 것이 있음)
- 에러의 경우 (입력 인자가 중복되는 경우, 입력 인자가 정수 범위를 초과하는 경우, 일부 인자가 정수가 아닌경우) 에는 "Error\n"를 표준 에러에 출력해야함.
$> ./push_swap 2 1 3 6 5 8
sa
pb
pb
pb
sa
pa
pa
pa
$> ./push_swap 0 one 2 3
Error
$>-
< bonus part >
- checker라는 이름의 프로그램을 작성해야 함.
- 이 프로그램은 정수의 리스트 형태로 된 스택 a를 인자로 받는다.
- 첫 번째 인자가 스택의 탑이 된다.
- 인자가 주어지지 않는다면 checker 프로그램은 종료되고 화면에 아무 것도 출력하지 않는다.
- checker는 명령어들을 표준입력으로 읽는다.
- 각각의 명령어들은 '\n' 뒤에 나온다.
- 명령어를 읽으면 checker는 인자로 받은 스택에 실행할 것이다.
- 명령어들을 실행하고 나서 스택 a가 정렬 되었고, 스택 b는 비어있는 상태이면 checker는 'OK\n'을 표준 출력에 출력함.
그게 아니라면 'KO\n'를 표준 출력에 출력함. - 에러(인자가 정수가 아닌경우, 인자가 정수범위를 벗어난 경우, 입력인자의 중복이 있는 경우, 명령어가 존재하지 않는 경우)가 난 경우에는 'Error\n'를 표준에러에 출력함.
$> ./checker 3 2 1 0
rra
pb
sa
rra
pa
OK
$> ./checker 3 2 1 0
sa
rra
pb
KO
$> ./checker 3 2 one 0
Error
$>
21세기 모험가