push_swap (2 step - 프로젝트 분석 및 구현 개요)(작성중)

1. 고려해야할 점

• 매개변수로 문자열을 입력받는데,
  • 이 변수들이 1 2 3 4 이렇게만 들어오면 argc-1로 총 인자 갯수를 정할 수 있다.
    
  • but, 만약에 1 2 3 "4 5 6" 이런식으로 들어오면 총 인자 갯수는 6개 이지만 argc - 1값은 4가 되어 정확한 총 인자 갯수를 정할 수 없다.

(example)

 $> ./push_swap 1 2 3 4 // argc - 1 = 4
 
 $> ./push_swap 1 2 3 "4 5 6" // argc - 1 = 4

< 해결 아이디어 >
: 인자 갯수를 바로 파악할 수 없기 때문에 차라리 변수를 하나하나 받아서 space를 기준으로 나누어 atoi한 1개의 정수를 저장할 연결리스트 구조체를 할당해서 저장한 후 이들을 이어주면 될 것 같다.

• 명령어 집합들을 보면 스택 중간에 있는 원소들을 이동시키는 연산이 없다.
  • 전부 맨 위와 맨 아래 원소, 즉 head와 tail에 위치한 원소를 가지고 이동한다.

< 해결 아이디어 >
: 단방향 연결리스트보다는 원형 연결리스트형식의 자료구조가 명령어 연산을 통해 원소들을 이동시키기 용이할 것 같다.

• 최소한의 명령어(원소간 이동)로 정렬을 해야하므로 정렬 최적화 알고리즘이 필요하다.
  • 버블정렬, 삽입정렬, 선택정렬은 시간 복잡도가 N(O^2)이므로 원소가 많을 수록 명령어 횟수가 비약적으로 커짐

<해결 아이디어>
: 시간 복잡도가 상대적으로 적은 quick sort나 merge sort를 사용하는게 좋을 것 같다. 둘 중에 quick sort를 선택해서 구성해보자.