[42 Seoul] push swap

설명에 들어가기 전 후기

2서클 중 가장 어려운 과제였기에 시간도 제일 오래 걸렸다

오래 걸린만큼 push_swap에서 나올 수 있는 웬만한 에러들은 다 만나고 끝낼 수 있었던 것 같다

정렬이 목적인 push_swap이지만 편의상 stack이라고 말하는 deque를 구현하는 법도 배울 수 있었고, 일반적인 정렬과 방법이 조금 다른 push_swap만의 여러가지 정렬 방법도 모두 맛볼 수 있었다

이것저것 많이 질문을 하러 다녔었는데, 그럴때마다 다들 도와주셔서 모두들 감사하다:)

 

프로젝트 소개

스택에 들어있는 데이터를 제한된 명령어를 사용하여, 최대한 적은 횟수 내에 정렬하기

• 스택 a, 스택 b
• 명령어(sa, sb, ss, pa, pb, ra, rb, rr, rra, rrb, rrr)

 

명령어

• sa: 스택 a의 top에 위치한 두 개의 원소의 순서 바꾸기
• sb: 스택 b의 top에 위치한 두 개의 원소의 순서 바꾸기
• ss: sa와 sb 동시에 수행
• pa: 스택 b의 top에 위치한 원소 한 개를 스택 a의 top으로 이동
• pb: 스택 a의 top에 위치한 원소 한 개를 스택 b의 top으로 이동
• ra: 스택 a의 원소를 한 칸씩 위로 이동
• rb: 스택 b의 원소를 한 칸씩 위로 이동
• rr: ra와 rb를 동시에 수행
• rra: 스택 a의 원소를 한 칸씩 아래로 이동
• rrb: 스택 b의 원소를 한 칸씩 아래로 이동
• rrr: rra와 rrb를 동시에 수행

 

그리디로 해결하는 방법

나는 그리디 방식을 사용했다

그리디란 탐욕 알고리즘이라고도 하며, 선택의 순간마다 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다

 

그리디에서 중요한 키워드는 2가지 있다

• 인덱싱
• 스택 a는 항상 정렬된 상태 유지

 

push swap을 그리디 방식으로 풀기 위해서는 인덱싱 과정이 필요하다

만일 값이 10, 12, 11 인자로 들어온다면 -> 0, 2, 1로 인덱스값을 가지게 한다는 뜻이다

인덱싱이 필요한 이유는 최종적으로 정렬할 때 굉장히 유용하기 때문이다

 

스택 b에서 어떤 값을 이동시켜야하는지 정하는 것이 그리디 방법의 핵심이다

• 스택 b의 요소들을 다 검사하면서, 각 요소마다 스택 a에 정렬되려면 몇 개의 명령어를 사용하는지 계산
  • 스택 a에서의 명령어 수 + 스택 b에서의 명령어 수 
• 가장 적은 명령어 수를 사용하는 요소를 스택 a로 이동

 

 

동작 순서

 

1. 인자값이 유효한지 검사 후 스택 a에 저장

2. 정렬이 되어있는지 확인

3. 정렬이 되어있지 않으면 인덱싱 과정 진행

4. 인덱싱 후 3등분하여 값을 스택 a와 스택 b에 저장

5. 스택 a에 3개의 수 만 있게 한 후, 나머지는 다 스택 b로 이동

6. 스택 a의 수를 정렬

7. 스택 b에서 최적의 값을 찾아 스택 a에 위치시킴

8. 최종적으로 정렬

9. 정렬 끝