push_swap 들어가기 전, 데이터 전처리, 알고리즘 생각

이 페이지에서는 push_swap 알고리즘 전에 데이터 전처리와 과제에서 요구하는 것을 볼 것임.

과제 설명

과제 설명

→ 쉽게 말해서 스택 a,b가 주어지는데 입력값을 스택 a에 다 넣고 스택 b를 통해서 정렬을 해야하는 과제.

정렬을 해야하는데 조건이 있음

• sa : swap a - 스택 a의 top에 위치한 두 개의 원소의 순서를 맞바꿉니다.

스택 a가 비어있거나 원소가 1개만 있을 때는 아무 동작도 하지 않습니다.

• sb : swap b - 스택 b의 top에 위치한 두 개의 원소의 순서를 맞바꿉니다.

스택 b가 비어있거나 원소가 1개만 있을 때는 아무 동작도 하지 않습니다.

• ss - sa와 sb를 동시에 수행합니다.
• pa : push a - 스택 b의 top에 위치한 원소 한 개를 스택 a의 top으로 옮깁니다.
• 스택 b가 비어있을 경우에는 아무 동작도 하지 않습니다.
• pb : push b - 스택 a의 top에 위치한 원소 한 개를 스택 b의 top으로 옮깁니다.
• 스택 a가 비어있을 경우에는 아무 동작도 하지 않습니다.
• ra : rotate a - 스택 a의 원소를 한 칸씩 위로 옮깁니다.
• 스택의 첫 번째 원소는 맨 마지막 원소가 됩니다.
• rb : rotate b - 스택 b의 원소를 한 칸씩 위로 옮깁니다.
• 스택의 첫 번째 원소는 맨 마지막 원소가 됩니다.
• rr : ra와 rb를 동시에 수행합니다.
• rra : reverse rotate a - 스택 a의 원소를 한 칸씩 아래로 옮깁니다.
• 스택의 마지막 원소는 맨 첫 번째 원소가 됩니다.
• rrb : reverse rotate b - 스택 b의 원소를 한 칸씩 아래로 옮깁니다.
• 스택의 마지막 원소는 맨 첫 번째 원소가 됩니다.
• rrr : rra와 rrb를 동시에 수행합니다.

----------------------------------------------------------------------------------------------------------
Init a and b:
2
1
3
6
5
8
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec sa:
1
2
3
6
5
8
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec pb pb pb:
6 3
5 2
8 1
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec ra rb (equiv. to rr):
5 2
8 1
6 3
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec rra rrb (equiv. to rrr):
6 3
5 2
8 1
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec sa:
5 3
6 2
8 1
_ _
a b
----------------------------------------------------------------------------------------------------------
Exec pa pa pa:
1
2
3
5
6
8
_ _
a b
----------------------------------------------------------------------------------------------------------

 

데이터 전처리와 알고리즘 생각

이제 해야할 것들

1. 데이터 전처리
2. 구조체로 스택 구조를 어떻게 만들 것인가?
3. 알고리즘은 어떻게 할 것인가?

1. 데이터 전처리

밑에 인풋값들을 a에 스택에 넣을 때 에러 표시를 해야함.

suc부분의 입력값들은 에러 처리가 나면 안 됨.

"" 2 1 3 4 
Error

" "  2 1 3 4
Error

"--2 1 3 2 4"
Error

"-   2  1  3  4"
Error

"        - " 2 13 4
Error

2 1 2 3
Error

"      -  2      " 1 3 5 6
Error

"     2- " 1 5 3 2
Error

" 2-4" 1 5 2 3 
Error

"- 0"
Error

"-0 +0 0" 
Error

"-0"
Error

"+0"
Error
------------------------------

"-2 1 3 2 4"
suc

"        -2" 1 3 2 4
suc

 

 

메인문을 한 번에 보여주고 함수별로 설명해보쟝

main

함수별로 설명해보겠다.

1. check_input_split
   1. argv로 받은 인자들을 공백 기준으로 다 스플릿을 함 → array_split 투 포인터에 넣어줌
2. change_int
   1. array_split에 있는 값들을 하나씩 검사하면서 array에 넣어줄 것임. (array는 array_size만큼 말록함)
3. ft_free
   1. array_split 필요없으니 free

 

2. 구조체로 스택 구조를 어떻게 만들 것인가?

처음에 이중 원형 연결 리스트로 했다가 연산이 이루어지는 명령어들을 사용할 때 이해하기가 너무 어려워서 원형을 지우고 그냥 이중 연결 리스트로 다시 만들었다.

• 이중 원형 연결 리스트를 처음 만들다 보니 너무 힘들었음.. ㅠ.ㅠ

• 스택 2개 만들기
  • t_stack이라는 구조체를 통해 스택 a와 b를 만듦.
• stack_a_push_node
  • int형 배열 array와 array_size와 스택 a를 같이 넘겨줌
  • int형 배열 값들을 하나하나 t_node를 만들어서 붙여줌
  • a 스택 top에 다 넣어줌. a 스택 마지막 값에 bottom 넣어줌
• array는 이제 안 쓰니 free

3. 알고리즘은 어떻게 할 것인가?

나는 이번 과제를 통해 퀵소트와 합병정렬에 대해 공부하였고 42서울의 카뎃분이 만드신 모래시계 알고리즘도 함께 공부하였다.

처음에는 어떤 알고리즘으로 할지 고민을 하다 퀵소트에 대한 미련을 버리지 못해 퀵소트로 코딩을 하게 되었다.

 

• check_sorted
  • 만약 a스택 친구들이 정렬이 되어있으면 끝냄.
• sort_algorithm
  • 정렬이 되어있지 않으면 sort를 하는 알고리즘으로 간다.

 

-jaeyojun-