42Seoul [push_swap]

July 1, 2022

push_swap

요약: 이 프로젝트를 통해 여러분은 주어진 어떠한 스택에 대하여 제한된 명령어 집합을 가능한 한 적게 사용하여 정렬할 수 있다. 성공적으로 프로젝트를 끝내기 위해서는 다양한 유형의 알고리즘을 조작하고 최적화 된 데이터 정렬에 가장 적합한 솔루션을 선택해야 한다.

Push_swap 프로젝트는 매우 간단하고 효과적인 알고리즘인 정렬에 관한 프로젝트이다. 정수값들의 집합, 2개의 스택 그리고 두 스택을 조작하기 위한 명령어 집합이 주어진다.
목표는? push_swap 이라는 프로그램을 C언어로 작성하는 것이다. 입력 받은 정수 인자들을 정렬하는 push_swap 명령어를 사용하여 가장 작은 프로그램을 계산하고 표준 출력에 출력한다.

이번 과제에서는 자료구조, 알고리즘(복잡도)를 중점으로 잡고 공부해나가면 된다.

이 프로젝트는 실제 사람에게만 평가될 것이다. 그러므로 파일 이름을 원하는대로 설정해도 된다. 그렇다하여도 아래에 있는 요구사항들을 준수하여야 한다.
실행 파일의 이름은 push_swap으로 지어야 한다.
Makefile을 제출해야 한다. Makefile은 반드시 프로젝트를 컴파일해야 하고 기본적인 rule들을 포함해야 한다. 프로그램이 필요시에만 재컴파일 돼야 한다.
여러분이 재치있게 해냈다면 이 프로젝트에 라이브러리를 포함할 것이다. libft 폴더와 그 안에 자체 Makefile을 넣어서 제출해라. Makefile은 라이브러리와 프로젝트 모두 컴파일해야 한다.
전역 변수의 사용은 금지되어 있다.
프로젝트는 Norm에 기반한 C로 작성돼야 한다.
여러분은 세심하게 에러를 처리해야 하며, 작성된 프로그램은 예상치 못한 방식으로 종료되면 안된다. (Segmentation fault, bus error, double free 등)
모든 프로그램은 메모리 누수가 나서는 안 된다.
필수 파트에서는 다음 함수들의 사용이 허용된다.

사용 가능한 함수
write
read
malloc
free
exit

규칙

이 게임은 a와 b라는 이름의 두 개의 스택으로 이루어져 있다.

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

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

b는 비어있다.

목표는 스택 a에 오름차순으로 수를 정렬하는 것이다.

sa : swap a - 스택 a의 가장 위에 있는 두 원소(혹은 첫 번쨰 원소와 두 번째 원소)의 위치를 서로 바꾼다.
sb : swap b - 스택 b의 가장 위에 있는 두 원소(혹은 첫 번쨰 원소와 두 번째 원소)의 위치를 서로 바꾼다.
ss : sa와 sb를 동시에 실행한다.
pa : push a - 스택 b에서 가장 위(탑)에 있는 원소를 가져와서, 스택 a의 맨 위(탑)에 넣는다. 스택 b가 비어 있으면 아무 것도 하지 않는다.
pb : push b - 스택 a에서 가장 위(탑)에 있는 원소를 가져와서, 스택 b의 맨 위(탑)에 넣는다. 스택 a가 비어있으면 아무 것도 하지 않는다.
ra : rotate a - 스택 a의 모든 원소들을 위로 1 인덱스 만큼 올린다. 첫 번째 원소(탑)는 마지막 원소(바텀)가 된다.
rb : rotate b - 스택 b의 모든 원소들을 위로 1 인덱스 만큼 올린다. 첫 번째 원소(탑)는 마지막 원소(바텀)가 된다.
rr : ra와 rb를 동시에 실행한다.
rra : reverse rotate a - 스택 a의 모든 원소들을 아래로 1 인덱스 만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.
rrb : reverse rotate b - 스택 b의 모든 원소들을 아래로 1 인덱스 만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.
rrr : rra와 rrb를 동시에 실행한다.

push_swap 프로그램

push_swap이라는 이름의 프로그램을 작성해야 한다. 이 프로그램은 스택 a에 들어갈 값들을 정수 리스트의 형태로 포맷팅하여 인자로 받는다. 첫 번째 인자는 스택의 탑이 된다(순서에 유의해라).
프로그램은 반드시 스택 a를 정렬하는데 가능한 가장 작은 개수의 명령어 리스트를 출력해야 한다.
명령어들은 ‘\n’으로만 구분되어야 한다.
목표는 가능한 적은 개수의 명령어 집합으로 스택을 정렬하는 것이다. 평가 도중에는 프로그램에서 도출한 명령어의 수와 허용된 최대 작업수를 비교한다. 프로그램에 너무 큰 리스트가 표시되거나 목록이 제대로 정렬되지 않은 경우 점수를 얻지 못한다.
에러의 경우에는, Error와 줄바꿈을 표준 에러에 출력해야 한다. 에러는 다음 예시들을 포함한다: 일부 인자가 정수가 아니거나, 정수 범위를 초과하거나, 중복이 있는 경우이다.

$> ./push_swap 2 1 3 6 5 8
sa
pb
pb
pb
sa
pa
pa
pa
$> ./push_swap 0 one 2 3
Error
$>

디버깅 && 체크

$>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_OS 프로그램이 KO를 출력하면, push_swap의 명령어 리스트가 정수 리스트를 정렬하지 못했음을 의미한다. checker_OS 프로그램은 인트라넷 프로젝트에 있다. 이 문서의 보너스 파트에서 동작 방식에 대한 설명을 찾을 수 있다.

시작하기 전 필요한 정보들

이 과제는 정렬에 관한 과제이기 때문에 옜날에 정리해둔 정렬알고리즘을 참고하면 도움이 된다.

이 프로그램의 정렬 순서는 입력값 순서대로 리스트의 꼬리로 삽입되고 정렬 후 에는 내림차순 정렬이 완료되어야 한다.

ex) ./push_swap 3 2 1 -> 1 2 3

알고리즘 복잡도(차수)

위에 링크에 설명이 나와 있지만 조금 더 세밀한 설명이 필요하다.

복잡도를 공부해야하는 이유는 주어지는 구성마다 가장 효율적인 정렬방식이 다르기 때문에 복잡도를 고려해야한다.

정렬 알고리즘	시간복잡도(최선)	시간복잡도(평균)	시간복잡도(최악)	공간복잡도(최악)
퀵 정렬	O(n log n)	O(n log n)	O(n²)	O(n)
병합 정렬	O(n log n)	O(n log n)	O(n log n)	O(n)
힙 정렬	O(n log n)	O(n log n)	O(n log n)	O(1)
거품 정렬	O(n)	O(n²)	O(n²)	O(1)
삽입 정렬	O(n)	O(n²)	O(n²)	O(1)
선택 정렬	O(n²)	O(n²)	O(n²)	O(1)

효율성을 고려해서 정리하자면

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

위의 효율성을 고려하여서 올바른 정렬을 선택하면 된다.

정렬 전 준비

문자열 파싱 및 검사
에러 체크
명령어 만들기

들어온 문자열 파싱 및 검사

int main(int argc, char *argv[])

들어오는 값은 문자얼 이차원 배열로 공백을 기준으로 구분되어 들어온다.

ex) ./push_swap 3 2 1 “4878 235”

argv[0][0]: .
argv[0]: ./push_swap argv[1]: 3 argv[4][4]: ` ` argc[4]: 4878 235

위 기준처럼 끊켜서 들어오게 된다.

따로 기준이 정해져 있는 입력이 아니라 문자열 처리는 spilt으로 처리해야 한다.

argv[0]은 프로그램 이름이니 제외
순차적으로 argc를 통해 argv를 검사
argv[i]마다 ft_split으로 통해 똑같이 null까지 검사
위 루틴에서 중복, overflow, 숫자검사
문제가 없다면 리스트 뒤에 삽입

while (i < argc)
	{
		ch_arr = ft_split(argv[i], ' ');
		if (!ch_arr)
		{
			free_list(head_a);
			error_format("malloc_failed");
		}
		j = 0;
		while (ch_arr[j])
		{
			list_error_check(head_a, ch_arr[j]);
			temp = ft_lstnew(ft_atoi(ch_arr[j++]));
			ft_lstadd_back(head_a, temp);
		}
		i++;
		free_array(ch_arr);
	}

삽입한 스택을 순회하며 정렬이 된건지 한번 체크한다.

3 그리고 5에 대한 처리

앞서 선택한 스택에 들어온 문자열을 파싱 후 삽입했다면 해당 크기는 ft_lstsize를 통해 알 수 있다.

해당 크기에 맞는 정렬은 거의 기준이 정해져 있기 때문에 하드코딩을 통해 정렬을 해야한다..

에러체크

따로 체크해야하는 사항은 오버플로우, 숫자가 아닌경우, 중복으로 세가지에 맞는 함수를 만든다.

파싱중 나는 에러는 해당 함수에서 처리

int	ft_isnum(char *str)
{
	int	i;

	i = 0;
	if (str[i] == '-')
		i++;
	if (ft_strlen(str) == 1 && str[0] == '-')
		return (0);
	while (str[i])
	{
		if (!ft_isdigit(str[i]))
			return (0);
		i++;
	}
	return (1);
}

int	ft_lst_overlap_check(t_list *head, int num)
{
	t_list	*temp;

	temp = head;
	while (temp)
	{
		if (temp->content == num)
			return (1);
		temp = temp->next;
	}
	return (0);
}

int	ft_lst_sorted_check(t_list *head)
{
	while (head)
	{
		if (head->next)
		{
			if (head->content > head->next->content)
				return (0);
		}
		head = head->next;
	}
	return (1);
}

에러 포맷함수

void    error_format(char *error_msg)
{
    ft_putstr_fd("error\n", 1);
    if (!ft_strncmp("non_numberic", error_msg, ft_strlen(error_msg)))
        ft_putstr_fd("A non-numeric value has been entered.\n", 1);
    else if (!ft_strncmp("overflow", error_msg, ft_strlen(error_msg)))
        ft_putstr_fd("int type overflow occurred.\n", 1);
    else if (!ft_strncmp("Duplicate", error_msg, ft_strlen(error_msg)))
        ft_putstr_fd("Duplicate value found.\n", 1);
    else if (!ft_strncmp("malloc_failed", error_msg, ft_strlen(error_msg)))
        ft_putstr_fd("Dynamic assignment failed.\n", 1);
    exit(1);
}
void    list_error_check(t_list **head, char *arg)
{
    if (!ft_isnum(arg))
        error_format("non_numberic");
    if (ft_atoi(arg) == -1 && ft_strlen(arg) > 2)
        error_format("overflow");
    if (ft_lst_overlap_check(*head, ft_atoi(arg)))
        error_format("Duplicate");
}

이런식으로 오류에 대한 체크를 따로 만들었지만 이후에 Error만 출력해야 한다는 것을 알아서 수정했다..ㅠ

표준에러체크 2의 값으로 fd를 념겨줘야한다.

두가지를 수정하여 에러 포맷을 만들것

free

사용되는 구조체가 단일연결 리스트로 해당 free함수 하나, 정수 배열 free함수 하나를 미리 만들어 준다.

void	free_list(t_list **head)
{
	t_list *temp;

	while (*head)
	{
		temp = *head;
		*head = (*head)->next;
		free(temp);
	}
}

void	free_array(char **arr)
{
	int	i;

	i = 0;
	while (arr[i])
	{
		free(arr[i]);
		i++;
	}
	free(arr);
	arr = NULL;
}

NULL은 gcc에서 오류로 잡아서 댕글링포인터를 막기위해 넣었는데 빼도 문제는 없는것 같다.

명령어 제작

sa, sb, ss, pa, pb, ra, rb

총 8개의 명령어를 제작한다. rr, rrr도 있지만 일단은 제외한다.

push_swap관련 명령어

static void push_to_stack(t_list **src, t_list **dst)
{
    t_list  *temp;
    temp = *src;
    if (*src)
        *src = (*src)->next;
    ft_lstadd_front(dst, temp);
}
void    call_push(t_list **head_a, t_list **head_b, int type)
{
    if (type == A)
    {
        push_to_stack(head_b, head_a);
        ft_putstr_fd("pa\n", 1);
    }
    else if (type == B)
    {
        push_to_stack(head_a, head_b);
        ft_putstr_fd("pb\n", 1);
    }
}
static void swap_to_stack(t_list **head)
{
    t_list  *temp;
    temp = *head;
    temp = temp->next;
    (*head)->next = temp->next;
    temp->next = *head;
    *head = temp;
}
void    call_swap(t_list **head, int type)
{
    if (type == A)
    {
        swap_to_stack(head);
        ft_putstr_fd("sa\n", 1);
    }
    else if (type == B)
    {
        swap_to_stack(head);
        ft_putstr_fd("sb\n", 1);
    }
}

실제 동작함수는 static으로 가려두고 해당 type과 head를 받아서 수행한다.

static void	rotate_to_stack(t_list **head)
{
	t_list	*temp_1;
	t_list	*temp_2;

	temp_1 = *head;
	temp_2 = *head;
	while (temp_2->next)
		temp_2 = temp_2->next;
	*head = (*head)->next;
	temp_1->next = NULL;
	temp_2->next = temp_1;
}

void	call_rotate(t_list **head, int type)
{
	if (type == A)
	{
		rotate_to_stack(head);
		ft_putstr_fd("ra\n", 1);
	}
	else if (type == B)
	{
		rotate_to_stack(head);
		ft_putstr_fd("rb\n", 1);
	}
}

static void	reverse_rotate_to_stack(t_list **head)
{
	t_list	*temp_1;
	t_list	*temp_2;

	temp_1 = *head;
	temp_2 = *head;
	while (temp_2->next)
		temp_2 = temp_2->next;
	while (temp_1->next != temp_2)
		temp_1 = temp_1->next;
	temp_1->next = NULL;
	temp_2->next = *head;
	*head = temp_2;
}

void	call_reverse_rotate(t_list **head, int type)
{
	if (type == A)
	{
		reverse_rotate_to_stack(head);
		ft_putstr_fd("rra\n", 1);
	}
	else if (type == B)
	{
		reverse_rotate_to_stack(head);
		ft_putstr_fd("rrb\n", 1);
	}
}

회전과 역회전또한 똑같은 형태로 만들어 준다.

이렇게 총 8가지를 사용한다.

필요한 유틸함수

마찬가지로 단일연결 리스트의 형태를 고려해야 일반화 함수를 만든다.

//헤더파일
#define A 0
#define B 1
#define CONTENT 0
#define INDEX 1
//

int	lst_max(t_list *head, int type)
{
	int		max;
	int		index;
	int		i;

	max = head->content;
	index = 0;
	i = 0;
	while (head)
	{
		if (head->content > max)
		{
			max = head->content;
			index = i;
		}
		head = head->next;
		i++;
	}
	if (type == INDEX)
		return (index);
	else if (type == CONTENT)
		return (max);
	return (-1);
}

int	lst_min(t_list *head, int type)
{
	int		min;
	int		index;
	int		i;

	min = head->content;
	index = 0;
	i = 0;
	while (head)
	{
		if (head->content < min)
		{
			min = head->content;
			index = i;
		}
		head = head->next;
		i++;
	}
	if (type == INDEX)
		return (index);
	else if (type == CONTENT)
		return (min);
	return (-1);
}

해당 헤더파일에 define해둔 상수값으로 type을 구분한다.

스택에서 가장 작은 값의 index, content를 알아오는 함수
스택에서 가장 큰 값의 index, content를 알아오는 함수

int	lst_get(t_list *head, int type, int var)
{
	int	i;

	i = 0;
	while (head)
	{
		if (type == CONTENT)
		{
			if (i == var)
				return (head->content);
		}
		else if (type == INDEX)
		{
			if (head->content == var)
				return (i);
		}
		head = head->next;
		i++;
	}
	return (-1);
}

스택에서 원하는 (값 or index)를 알아오는 함수

위의 유틸함수들을 잘 조작하면 원하는 위치의 값을 얻을 수 있다.

크기가 3인 스택 정렬

크기가 3이기 때문에 스택을 하나만 써서 정렬힌다.

정렬이 된 스택인지 검증하는 루틴을 반복문으로 걸어준다.(탈출의 경우 정렬 끝)

3인 경우의 경우의 수는 총 (1 2 3, 1 3 2, 2 1 3, 2 3 1, 3 2 1, 3 1 2) 6가지이다.

하지만 앞서 정렬된 경우에 대한 예외처리가 존재하기 때문에 해당 정렬의 경우의 수는 5가지이다.

5가지에 대한 정렬을 미리 정리해보자..

1 3 2

sa: 3 1 2
ra: 1 2 3

2 1 3

sa: 1 2 3

2 3 1

rra: 1 2 3

3 2 1

ra: 2 1 3
sa: 1 2 3

3 1 2

ra: 1 2 3

위 처럼 명령어가 실행되어야 가장 최소 조건이다.

공통점

가장 큰 값(max)가 탑위치 일 경우 ra로 바텀위치로 한칸씩 밀어준다.

가장 작은 값(min)뒤로 가장 큰 값(max)이 있는 경우 sa둘의 위치를 바꿔준다.

가장 큰값 뒤로 가장 작은 값이 있는 경우 rra로 전체적으로 한칸씩 내려준다.

크기가 3이상 5이하인 스택 정렬

처음의 아이디어로 4~5개의 경우이니 3의 최소값으로 2개를 b스택으로 push해주고 나머지를 3이하 정렬 알고리즘으로 보내서 정렬하게 한다.

그리고 b스택이 남아있을 때 까지 반복하면서 a와 비교해 올바른 위치에서 push가 될 수 있도록 ra, rra를 통해서 돌려준다.

// push로 a->b로 두번 넘김
while(*head_b)
{
	// b의 첫번째 숫자가 a의 가장 큰값보다 작고 가장 작은값보다 크다면 
    // b의 첫번째 숫자가 a의 두번째 숫자보다 작고 첫번째 숫자보다 크다면 첫번째와 두번째사이에 삽임
	// b의 첫번째 값이 a의 첫번째 값보다 작으면 안되고 b의 첫번째 값이 a의 마지막 값보다 크지 않을 때 까지
	// ---
	// 다시한번 정렬
}

크기가 크게 가변적이지 않고 위 아래의 크기가 다르기 때문에 ra, rra의 명령어 선택을 잘해야 한다.

크기가 5이상인 스택

우선 이 과제의 핵심은 가장 명령어를 적게 사용하여 스택 a에 정렬하는 것 이기 때문에 내부에서 동작하는 과정은 상관이 없다.

따라서 해당 리스트에 있는 값을 배열로 복사하여 따로 정렬하고 해당 정렬된 데이터를 바탕으로 정렬해도 문제가 없는것이다.

배열에 스택을 복사하여 퀵소트를 실행한다.

quick_sort

분할통치법의 대표적인 예로 재귀형태를 가진 정렬이다.

static void	swap(int *x, int *y)
{
	int	tmp;

	tmp = *x;
	*x = *y;
	*y = tmp;
}

static int	partition(int *arr, int low, int high)
{
	int	pivot;
	int	i;
	int	j;

	j = low;
	i = (low - 1);
	pivot = arr[high];
	while (j <= high - 1)
	{
		if (arr[j] < pivot)
		{
			i++;
			swap(&arr[i], &arr[j]);
		}
		j++;
	}
	swap(&arr[i + 1], &arr[high]);
	return (i + 1);
}

void	quick_sort(int *arr, int low, int high)
{
	int	pi;

	if (low < high)
	{
		pi = partition(arr, low, high);
		quick_sort(arr, low, pi - 1);
		quick_sort(arr, pi + 1, high);
	}
}

위 방법대로 정렬된 배열을 사용한다.

정렬

스택 a가 비어질 때 까지 전부 b스택으로 보낸다.
- 퀵정렬로 정렬된 배열의 중간 값(or 분할값)을 찾고 해당 값 보다 작다면 a로 보내는 작업을 반복
- a로 보낼때도 스택을 아래에서 접근하거나 위에서 접근했을 때 효율을 비교하여 보냄
스택 b가 정렬되었다면 해당 b는 일부분 정렬된 상태
- 100~80, 80~60 .. 이런형태
스택 b위에서 부터 접근하여 rb, rrb 명령어를 통해 회전 시키며 max값을 a로 push

이런 형태로 정렬을 하면 끝난다.

Twitter Facebook LinkedIn

Lee Jeongan