[42Seoul/push_swap] 최적화는 어떻게 하는데요?

우선 결과를 보여드리겠습니다

100개 기준

 

500개 기준

 

5개 기준

3개 기준

 

---

3개 기준 최대 2개

5개 기준 최대 10개

100개 기준 550개 정도

500개 기준 4400개 정도

 

다른 사람들이 pivot 2개 잡고 quick sort로 반복문 할 때, 다른 게 하고 싶은 마음이 들어서 하게된 알고리즘 선택

우선 메인이 되는 부분을 설명을 시작하면 LIS 그리고 최적화

 

LIS : 최장 증가 부분 수열 알고리즘

들어온 인자를 순회하면서 제일 긴 오름차순을 찾아낸다.

LIS에 해당하는 숫자의 경우는 ra 명령어를 실행, 아닌 경우는 pb 명령어를 실행

비교는 하지 않았지만, 100개 이상의 경우는 중앙값보다 작으면 pb, rb를 실행

 

LIS를 이용한 a to b

a 스택은 정렬이 되어 있는 상황

a to b

b to a 를 하기 위한 최적화

b스택에 있는 부분은 공통적인 pa를 제외한 명령어를 구하게 된다

pa로 넘겼을 때, 오름차순 정렬은 하지 않고 최소값기준으로 봤을 때, 정렬이 되어 있는 상황이라면 OK

 

넘기는 숫자들의 경우의 수는 총 4가지이다.

• ra + rb
• rra + rb
• ra + rrb
• rra + rrb

rr과 rrr을 이용하여 최적화를 진행할 수 있다. 예를 들어서 이야기 하면

ra + rb = 7 을 실행하기보다는 ra + rr = 4와 같이 명령어 횟수를 줄여서 진행할 수 있게 된다.

이러한 경우의 수의 값을 구해서 sum이 최솟값이 숫자를 체크

b스택에 담겨있는 숫자의 위에서 언급된 4가지의 최솟값을 구하면

반복문을 통해 모든 숫자들이 넘어갈 수 있는 최솟값을 구하면, 제일 적은 숫자로 넘길 수 있는 숫자를 확인할 수 있게 된다.

그렇게 정해진 명령어를 실행하고 마지막에 pa로 숫자를 넘기면 끝!

 

 

b to a 의 진행은 b스택의 size가 0이 될 때까지 반복을 하게 된다.

남은 3을 넘기게 되면 명령어를 몇 번 사용하고  a스택은 어떻게 보일까?

한 번 고민을 해보고 펼치기를 해보자

 

답은 rra 2번 (공통 pa 1번 제외)

 

이제 정렬이 되어가는 모습이 보이지 않나요?

마지막으로 최솟값이 top으로 오려면 제일 적은 명령어를 실행하게 되는데,

위에까지 이해를 했으면 이 다음은 쉬운 수준이니 PASS

 

그럼 이미 어떻게 만들어야 되는지 설명이 끝나버렸다

참 쉽죠?

 

파싱에 대한 이야기와 보너스에 대한 이야기는 앞서 이야기한 것보다 더 짧게 간략하게 말을 하고 글을 마칠게요

배열로 구현하거나 연결리스트로 구현을 하여서 사용을 해도 되는데, 작년에 만들어 놓았던 내용이 있어서

원형 양방향 연결리스트로 구현을 했어요.

 

파싱에서 조심해야 되는 부분

빈 문자열, 공백만 있는 문자열, 숫자가 아닌 문자열

//Error
./push_swap "" 1

./push_swap "    " 3

./push_swap -

./push_swap 1 "a " 4

./push_swap 3 1 3

./push_swap (MAX_INT + 1)의 값

//아무것도 실행되지 않음
./push_swap 1 2 3

./push_swap 4

 

 

보너스의 경우

들어온 값을 먼저 스택에 넣어놓고

입력받은 명령어를 gnl을 이용해서 인식하고 실행을 하고 제대로 정렬이 되어있는지, 아닌지 OK, KO로 표현을 해주면 된다.

(여기에도 Error인 경우가 있으니 참고하여서 만들면 된다)

 

진짜 끝!!

 

subject 내용은 이전 글에서

2021.09.21 - [42 Seoul] - [push_swap] 정렬에 대한 공부 / 42 SEOUL

[push_swap] 정렬에 대한 공부 / 42 SEOUL