push_swap

개요 : push_swap이란?

A와 B라는 두 개의 스택이 주어진다.
스택 A에는 임의의 개수의 정수들이 중복 없이 채워져 있다.
스택 B는 비어 있다.
스택 A와 B, 그리고 적절한 "연산"을 통해 A의 숫자들을 오름차순으로 정렬해야 한다.
다음과 같은 연산이 주어진다.
- sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr
최소한의 연산만을 사용해 A의 숫자들을 정렬

mandatory는 다음과 같이 나오면 된다. (숫자를 집어 넣고, 어떻게 연산을 해서 정렬했는지를 출력)

bash

$ ./push_swap 1 2 3 4 5 "10 14"
> sa
> sb
> ss
> pa
> pb

1. Parsing & Check 1

입력은 다음과 같이 주어진다.

bash

./push_swap 1 2 3 4

argument count와 argument vector를 사용

에러출력 상황

다음과 같은 상황에서 Error를 표출해야 한다.

입력값이 숫자가 아닌 경우
입력값이 int 범위를 초과한 경우
입력값에 중복이 있을 경우

체크하기 1

각 argument vector의 원소(=문자열) 확인

확인 케이스

bash

./push_swap 1 2 3 4      # 숫자 1개가 있는 문자열 
./push_swap 1 2 "3 5" 3  # 숫자 여러개가 있는 문자열
./push_swap              # 아예 빈 경우
./push_swap "1"         # 문자열 1개

만드는 방법

문자열을 받고, 쪼갠다. ft_split() 사용
이중포인터 체크
- 아예 빈칸을 체크하기 위한 요소
각 상자 안의 문자들을 체크
첫 번째 문자가 부호인지 체크
(이후 또는 현재) 문자가 숫자인지 체크

중간에 count 변수로 숫자를 세준다.
하나라도 조건에 맞지 않으면 0 반환

str → long으로 바꾸고, int 범위 내인지 체크

ft_strtol() 만들기
INT_MIN과 INT_MAX 정의
이후 int 범위 체크

체크하기

bash

./push_swap "1 3"
# count = 3
# ac = 2

count = (문자열에서 분리한 숫자 갯수) + (숫자 갯수)
ac = (입력받은 문자열 갯수)
ac == count이고, ac가 2보다 작으면 공백 출력
아니면 정상출력.

2. Stack & Check 2

스택 만들기 & 집어넣기

자료구조 : 덱(double-list queue)를 선택
연결리스트를 이용한 덱 생성
각 숫자를 덱에 집어넣기

체크하기 2

숫자들이 중복되었는지를 체크.

스택 → 배열로 옮긴 후 체크
- 스택 → 배열로 옮길 때, pop 계열 함수를 쓰면 절대 안 된다.
- 스택 자체가 빠져버리므로 이후 과정을 진행할 수 없음.
배열의 중복여부를 체크하는 함수 제작.
역시 잘못되었으면 에러 출력

체크하기 3

숫자들이 이미 정렬되었는지 체크
연결리스트를 돌면서 다음과 같이 체크
- 제일 처음 시작은 스택의 맨 윗 부분

(결과) = (지금노드->데이터) - (다음노드->데이터)
(결과)가 음수면
	minus += 1
양수면
	plus += 1

minus만 있고, plus == 0이면 정렬.
그렇지 않은 나머지 케이스는 전부 비정렬.

3. 연산 제작하기

rotate

스택 맨 위의 숫자를 스택 맨 아래로 보내는 명령어이다.

아래 그림은 ra(rotate a) 를 실행했다고 했을 때 나오는 결과이다.

bash

<before>
 front         rear 
--------------------
a) 1 2 3 4 6 7 8 9
b)

<after>
 front         rear 
--------------------
a) 9 1 2 3 4 6 7 8 
b)

reverse rotate

스택 맨 아래의 숫자를 맨 위로 보낸다.

push

한 쪽 스택의 맨 위 숫자를 다른 쪽 스택으로 보내는 명령어이다.

아래 그림은 pb(push b) 를 실행했다고 했을 때 나오는 결과이다.

bash

<before>
 front         rear 
--------------------
a) 1 2 3 4 6 7 8 9
b)

<after>
 front         rear 
--------------------
a) 1 2 3 4 6 7 8
b) 9

swap

스택의 맨 위 숫자와 바로 아래의 숫자를 바꿔준다.

bash

<before>
 front         rear 
--------------------
a) 1 2 3 4 6 7 8 9
b)

<after>
 front         rear 
--------------------
a) 1 2 3 4 6 7 9 8
b)

4. 알고리즘 - 그리디

algorithm 선택

여러가지 알고리즘이 있는 것으로 알려져 있다.

단, 여기서의 시간복잡도는 명령어 갯수를 의미하므로 생각

병합정렬 - 어떻게 병합할지 잘…
선택정렬 - 너무 느림. 원래 시간복잡도 콘셉과 잘 안 맞음.
퀵 정렬 - 저걸 어떻게 스택 2개로 구현할지 감이 안 옴.
그리디 - 이정도면 구현할 수 있겠다는 감이 옴.
- 모래시계 - 가장 대중적이나 이해 없이 막 쓰는 느낌.
- 3피봇 - 제일 이해하기 쉬웠음.

스택 A → 스택 B

피봇을 구한다. (스택 A의 노드 갯수가 3개 이상인 경우)
- 연결리스트 → 배열로 숫자를 옮긴다
- 배열을 정렬한 후 1/3, 2/3 지점을 구한다.
  - 해당 숫자가 있는 노드를 찾는다.
  - 그 숫자보다 작은 숫자를 가진 노드를 전부 스택 B로 넘긴다.
  - 1/3, 2/3 지점 모두 처리
- 나머지 숫자들을 숫자의 크기에 상관없이
  
  최하 3개만 남기고 전부 넘긴다.
남은 숫자 처리 (스택 A의 노드 갯수 ≤ 3)
- 하드코딩
- 5가지 케이스에 대한 정렬 실시

다시, 스택 A (part 1)

가장 힘들었던 과정이라고 할 수 있음.

기본 가정 : A는 무조건 정렬되어 있다.
B의 원소 한 개를 보내고 난 후에도 A는 무조건 정렬 상태.
즉 원소 한 개를 보낼 때의 연산 = B를 움직이는 연산 + A를 움직이는 연산 + A 원복 연산

이를 위해 연결리스트의 노드를 수정한다.

노드에 cost_a, cost_b, cost_total을 추가.

cost_b 구해보기

	stack_B    cost_B
---------------------
		0					 0
		1					 1
		2					 2
		3					 3
		4					-3
		5					-2
		6					-1
---------------------

전체 갯수를 count.
idx = 노드의 순서. 첫 번째는 스택의 맨 위: rear

if (idx <= count / 2)
	return (idx);
else
	return (idx - count);

cost_a 구하기

들어가야 할 자리가 어디인지 생각해 보자.

	stack_A     stack_B
-----------------------
		0					  0
		1					 70
		2					  2
		3					120
							 11
							 -2
							 -1
-----------------------

A는 항상 정렬되어 있다고 가정한다.

항상 정렬이 되어있다가 무조건 맨 위에 최소값이 온다는 것은 아니다.
A를 이때만큼은 원형이라고 생각하자. (실제로는 원형이 아니지만)

어떠한 방식으로 꺼내진 B의 노드 중 하나를 A의 어딘가에 끼워넣어야 한다.

그렇다면 B의 노드가 가진 숫자가 A의 특정 노드의 숫자보다 작다면, 그 자리에 넣으면 될 것이다.

nodeA -> stack A의 rear, 최상단.
nodeB -> 어떠한 방식으로든 꺼내진 B
min값은 LONG_LONG_MAX로 하는 것이 좋다.

while nodeA:
	if nodeB->data < nodeA:
		tmp = nodeB->data < nodeA
		if tmp < min:
			min = tmp;
			cost_a = idx;
	nodeA = nodeA->before;
	idx++;

만약, B의 노드가 가진 숫자가 A의 특정 노드의 숫자보다 크다면,

그래서 cost_a가 구해지지 않는다면, 노드를 while문으로 돌리면 A의 최대 노드를 찾으면 된다.

이것 역시 음수, 양수 구분을 해준다.

전체 갯수를 count.
idx = 노드의 순서. 첫 번째는 스택의 맨 위: rear

if (idx <= count / 2)
	return (idx);
else
	return (idx - count);

cost_total 구해보기

cost_total = cost_b + |cost_a|

다시, 스택 A (part 2)

다음과정을 스택B가 빌 때까지 진행한다.

cost_total이 가장 작은 노드를 고른다.
cost_B를 보고, 음수이면 rrb, 양수면 rb를 (cost_B의 절댓값)만큼 한다.
cost_A를 보고, 마찬가지로 진행.
B→A로 최상단 노드를 보낸다.

다시, 스택 A (part 3)

최적화를 위해 다음 기능을 추가했다.

만약, costA와 costB가 모두 같은 부호라면 어떨까?

이 경우 rrr()이나 rr()을 생각해 볼 수 있을 것이다.
우선 한쪽이 0이 될 때까지 rrr이나 rr을 돌린다.
그 이후, 상황에 따라서 ra/rb, rra/rrb를 돌린다.

이 방식을 통해 총 명령어 갯수를 상당히 줄일 수 있다.

마지막 정렬

숫자가 전부 스택A로 갔으면,

스택A의 최솟값을 가진 노드 찾는다.
역시 절반을 넘었는지 안 넘었는지 본다.
결과에 따라 rra나 ra를 실행한다.

5. 보너스

checker를 만드는 것이다.

정렬, 파싱, 스택에 넣기까지는 전부 mandatory와 같다.
while을 돌리면 get_next_line()을 이용해 명령어를 받는다.

get_next_line(0)을 해주면 계속 std_input에서 받을 수 있다.

중단하는 법은 ctrl + D = EOF를 보내주는 것이다.

엉뚱한 명령어가 들어가면 중단시키고 바로 Error를 보낸다.
정렬이 되었는지 판단하는 함수 (위에서 만든 것)로 노드의 정렬 여부를 확인한다.

6. 확인사항

정렬 여부 확인
leak 확인
norm 확인
최적 갯수 확인
- 3개 : 2번
- 5개 : 12번
- 100개 : 700번
- 500개 : 5500번

7. 데이터

X_{100} \sim N(640, ?) \\ X_{500} \sim N(4867, ?)

O(N^2)이 될 수밖에 없는 상황. 평균으로 계산하는게 좀 더 정확하지 않은가…?