과제 소개
Summary
이 프로젝트를 사용하면 가능한 가장 적은 수의 작업을 사용하여 제한된 지침 집합으로 스택에서 데이터를 정렬 할 수 있습니다.
성공하려면 다양한 유형의 알고리즘을 조작하고 최적화 된 데이터 정렬에 가장 적합한 솔루션을 선택해야합니다.
허용 함수
wirtereadmallocfreeexit
규칙
스택 a와 스택 b를 이용하여 인자로 들어온 숫자들을 오름차순으로 스택 a에 정렬한다.
- 시작:
a는 양수 또는 음수의 숫자들을 중복 없이 랜덤으로 가진다.
b는 비어있다.
다음과 같은 작업들을 수행할 수 있다.
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를 동시에 수행한다.
선행 지식
스아실 선행 지식까진 아니고 그냥 시작하기 전에 주워들은 것들,,
1. double linked list를 쓰면 편하다.
2. Quick Sort로 구현하면 더 높은 점수를 받을 수 있다.
그래서 나도 double linked list를 쓰려고 한다. 그게 넣고 빼고 옮기고 그러기에 편할 것 같다.
그리고 어떤 정렬 알고리즘을 사용할지 아직 확정하진 못했다. 이제 과제를 보기 시작했고 아직 아무런 작업도 안 했기 때문에 고민도 안 해보고 바로 퀵소트로 짜는 건 공부가 덜 될 것 같다. 솔직히 결국에는 퀵소트로 갈 것 같긴 한데, 그래도 스스로 고민해보는 시간을 가져보고 싶다.
사전 작업
Makefile
먼저 Makefile부터 만들었다. 멬파 이젠 뚝딱-!... 뚝딱 아님 뚝딱거리긴 함
Parsing
그리고 파싱작업을 했다. main()에 인자로 들어오는 숫자들이 사실은 문자열로 들어오기 때문에 변환해주는 작업이 필요하다. 또 int 범위 밖의 숫자가 들어온 경우, 12a 처럼 숫자가 아닌 문자가 들어왔을 경우 등을 걸러주는 작업도 필요하다.
먼저, 인자로 들어온 문자열의 맨 앞 문자가 +/- 처럼 부호인지 확인했다. 부호를 제외하고는 모든 문자가 숫자로 이루어져야 하며, 중간에 문자가 나왔을 때를 예외처리 했다.
그리고 int 범위 내의 숫자여야 하는데, long long으로 받아서 처리하자니 unsigned long long 범위가 신경쓰이고, 그렇다고 unsigned long long으로 하기엔 음수를 처리할 수 없어서 안되고... 참 난감한 상황이 아닐 수 없었다.
이 고민을 얘기하니까 hyunlee님이 본인이 한 방법을 공유해줬다. int의 최대값이 총 10자리 수니까, 들어온 인자가 부호 혹은 앞에 붙은 0을 제외하고 10자리 이내인지를 확인했다고 했다. 그러면 11자리부터의 큰/작은 숫자는 다 걸러줄 수 있다. 그리고 이 검사를 통과한 숫자들을 long long형으로 변환한 다음, INT_MAX 혹은 INT_MIN과 비교해서 int 범위 내의 숫자들만 리턴해준다.
아주 굿아이디어라고 생각했고 나도 그렇게 코드를 작성했다. 먼저 check_arg.c 에서 모두 숫자로 이루어져 있는지(부호 제외), 길이가 10자리 이내인지(부호와 앞에 붙는 0 제외)를 확인해서 그렇지 않으면 0을 리턴하고 유효한 숫자(아직 문자열이지만)이면 1을 리턴하는 함수를 작성했다.(check_arg())
그리고 ft_atoi()를 다시 만들어서, 가장 먼저 check_arg()를 호출해서 0이 리턴되면 exit(0)으로 함수를 끝내버렸다. 그리고 마지막에 숫자 변환이 끝나고 나서 그 숫자가 int 범위를 넘어가면 exit(0)으로 또 함수를 끝내버렸다.
인자 중에 하나라도 유효하지 않은 숫자가 들어오면 에러메세지를 출력하고 종료시키면 된다.
마무리
일단 오늘은 여기까지 했다.
알고리즘 과제를 하게 돼서 좋기도 한데 또 막상 하려니까 하기 싫기도 하고,, 어렵고 힘들 것 같아서ㅠ
그래도 어떡해~ 해야지.. 아자아자 새 과제도 열심히 하자~! (๑ •̀ㅂ•́ )و✧
