최적화가 필요한 이유
push_swap에서 사용되는 명령어들중 특정한 순서로 나오게되면 명령어를 호출하기 전과 똑같은 상태가 되거나 한번의 명령과 같아지는 경우가 있음
이러한 부분들을 명령어 스택에서 제거하거나 변경하여 호출되는 명령어를 최소화할 수 있도록 하는 과정
ex) ra->rra , rb->rrb, sa->sa, sb->sb 등
사용 명령어
- 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
a와 rb를 동시에 실행한다.- rra
reverse rotate a - 스택 a의 모든 원소들을 아래로 1 인덱스 만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.- rrb
reverse rotate b - 스택 b의 모든 원소들을 아래로 1 인덱스 만큼 내린다. 마지막 원소(바텀)는 첫 번째 원소(탑)가 된다.- rrr
rra와 rrb를 동시에 실행한다.
최적화가 필요한 경우
sa, sb, ss
- sa -> sa, sb -> sb = x
sa와 sb는 첫번째, 두번째 자리의 위치를 바꾸는 명령어인데 이를 두번 호출시 원점이므로 없어도 됨- sa -> ss, ss -> sa = sb
sa와 sb를 모두 실행하는 ss명령어 후 sa를 실행시 sb를 한번 호출한것과 똑같음- sb -> ss, ss -> sb = sa
sa와 sb를 모두 실행하는 ss명령어 후 sb를 실행시 sa를 한번 호출한것과 똑같음- sa -> sb, sb -> sa = ss
sa와 sb를 순서대로 실행하는경우 ss를 한번 호출한것과 똑같음
pa, pb
- pa -> pb, pb -> pa = x
a의 탑을 b의 탑으로 보내는 pb와 b의 탑을 a로 보내는 pa를 순서대로 실행하는 경우 원점이므로 없어도 됨
ra, rb, rr, rra, rrb, rrr
- ra -> rra, rra -> ra = x
a의 원소를 위로 1만큼 올린뒤 다시 1만큼 내리거나 그 반대라면 원점이므로 없어도 됨- rb -> rrb, rrb -> rb = x
b의 원소를 위로 1만큼 올린뒤 다시 1만큼 내리거나 그 반대라면 원점이므로 없어도 됨- ra -> rb, rb -> ra = rr
a와 b의 원소를 순서대로 올리는것은 rr명령어 한번으로도 가능함- rra -> rrb, rrb -> rra = rrr
a와 b의 원소를 순서대로 내리는것은 rrr명령어 한번으로도 가능함- rr -> rrr, rrr -> rr = x
a와 b의 원소를 올렸다가 내리거나 그 반대라면 원점이므로 없어도 됨- rr -> rra, rra -> rr = rb
a와 b의 원소를 모두 올리고 바로 a의 원소를 내리는것은 rb한번과 같음- rr -> rrb, rrb -> rr = ra
a와 b의 원소를 모두 올리고 바로 b의 원소를 내리는것은 ra한번과 같음- rrr -> ra, ra -> rrr = rrb
a와 b의 원소를 모두 내리고 바로 a의 원소를 올리는것은 rrb한번과 같음- rrr -> rb, rb -> rrr = rra
a와 b의 원소를 모두 내리고 바로 b의 원소를 올리는것은 rra한번과 같음
늅늅