Push Swap : 가장 작은 인자 정렬 프로그램을 계산하기

프로젝트 개요

 

Mandatory Part

입력받은 정수 인자들을 정렬하는 push_swap 명령어를 사용하여 가장 작은 프로그램을 계산하고 표준 출력에 출력한다.

이 프로그램은 a와 b라는 이름의 두 스택으로 이루어져 있다.

게임은 다음과 같은 상태에서 시작한다 :

a는 서로 중복되지 않는 음수 혹은 양수인 난수들을 포함한다.

b는 비어있는 상태.

 

목표는 스택 a에 오름차순으로 수를 정렬하는 것이다. (오름차순 : 작은 것부터 큰 것 순)

다음과 같은 연산들을 수행할 수 있다 :

1. sa(swap a) : 스택 a의 가장 위에 있는 두 원소의 위치를 서로 바꾼다. 원소가 하나있거나 없을 경우 아무것도 하지 않는다. 
2. sb(swap b) : 스택 b의 가장 위에 있는 두 원소의 위치를 서로 바꾼다. 원소가 하나있거나 없을 경우 아무것도 하지 않는다. 
3. ss : sa와 sb를 동시에 실행한다.
4. pa(push a) : 스택 b에서 가장 위(top)에 있는 원소를 가져와서, 스택 a의 맨 위에 넣는다. 스택 b가 비어있으면 아무것도 하지 않는다.
5. pb(push b) : 스택 a에서 가장 위(top)에 있는 원소를 가져와서, 스택 b의 맨 위에 넣는다. 스택 a가 비어있으면 아무것도 하지 않는다.
6. ra(rotate a) : 스택 a의 모든 원소들을 위로 1만큼 올린다. 첫번째 원소는 마지막 원소로 밀려내려온다.
7. rb(rotate b) : 스택 b의 모든 원소들을 위로 1만큼 올린다. 첫번째 원소는 마지막 원소로 밀려내려온다.
8. rr : ra와 rb를 동시에 실행한다.
9. rra(reverse rotate a) : 스택 a의 모든 원소들을 아래로 1만큼 내린다. 마지막 원소는 첫번째 원소로 밀려올라간다.
10. rrb(reverse rotate b) : 스택 b의 모든 원소들을 아래로 1만큼 내린다. 마지막 원소는 첫번째 원소로 밀려올라간다.
11. rrr : rra와 rrb를 동시에 실행한다.

 

• 피평가자는 push_swap이라는 이름의 프로그램을 작성해야 한다. 이 프로그램은 스택 a에 들어갈 값들을 정수 리스트의 형태로 포맷팅하여 인자로 받는다. 첫번째 인자는 스택의 top이 된다.
• 프로그램은 반드시 스택 a를 정렬하는데 가능한 가장 작은 개수의 명령어 리스트를 출력해야 한다.
• 명령어들은 '\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
$>

 

 

평가 시 42측이 제공한 바이너리를 사용하여 피평가자가 작성한 프로그램을 아래와 같이 사용할 것이다.

$>ARG="4 67 3 87 23"; ./push_swap $ARG | wc -l
6
$>ARG="4 67 3 87 23"; ./push_swap $ARG | ./checker_OS $ARG
OK
$>

checker_Mac 프로그램이 KO를 출력하면, push_swap의 명령어 리스트가 정수 리스트를 정렬하지 못했음을 의미한다.

 

---

이용한 알고리즘

 

분할정복법(divide and conquere)

 

정렬시키려고 넣은 수(이하 인자라 서술)가 2개이면 sa 하나로 정리 가능

인자가 3개일 경우, 하드코딩으로 마무리

인자가 4~5개 일 경우, 인자가 3개인 케이스에서 조금 더 확장된 하드코딩

인자가 6개 이상일 경우 b스택에 내림차순으로 후다닥 정렬하고 a스택에 pa로 옮김.

 

best_b(data) : n_moves()를 돌리면서 스택 a에서 가장 작은 이동 수를 구함. 

n_moves(data, i) : 

put_mid_b_count(data, i) : i의 2배보다 b스택의 크기가 더 크면 i, 아닐 경우 b스택의 끝과 i의 차이를 반환.

move_to_i(data, i) : a스택의 탑에 인덱스 i의 값이 오도록 함.

 

find_big(data) : b스택에서 가장 큰 수가 들어있는 index값을 구해서 반환

move_rev(data) : 가장 큰 수가 제일 위에 오도록 조정

rev_sort(data) : b스택이 내림차순(큰 수->작은수부터 차례대로 정렬)인지 확인. 

put_mid_b(data, i) : b스택의 i번째 수가 b스택의 0번째 자리에 오도록 조정해서, a스택의 가장 위에 있는 원소를 b스택 탑으로 옮김.

최종적으로 a스택 탑을 b스택 i번째 위에 올려놓는 작업 

move_b(data) : 

i_or_j(i, j) : j가 더 크거나 같을 경우 i를 반환, j가 작을 경우 두 수의 차이(음수)를 반환.