[Array] Sort Array By Parity

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

You may return any answer array that satisfies this condition.

Two-pointer 알고리즘을 사용하는 문제이다.

1차원 배열이 있고, 이들이 가리키는 원소가 각각 다른 케이스들만 조합해서 답을 찾아내는 경우에 사용한다.

(이러한 유형의 문제의 대표급은 특정 원소의 합이 주어진 value가 되는지 여부를 찾는 문제들!)

 

Two-pointer 알고리즘 관련 문제들은 보통 다음과 같이 해결한다

 

1) 포인터가 2개가 필요. A포인터는 항상 B포인터보다 작거나 같아야 한다.

2) A포인터와 B포인터의 초깃값은 각각 0과 Array.length-1로 설정한다

3) A<B에 대해서만 Loop를 돌린다.

4) 조건에따라 A는 늘려가면서, B는 줄여가면서 Loop를 돌린다

5) 그리고 수행이 끝날때마다 포인터를 바꿔준다(A포인터는 더해주고, B포인터는 빼준다)

 

이러한 종류의 문제를 이중Loop를 돌리게 되면 시간복잡도가 n^2이 되니까.. 코테 탈락이다

 

TwoPointer 알고리즘의 가장 대표 유형은 부분합이다.

for를 두번 돌리면 모든 원소에 대한 경우의 수를 다 체크하므로 비효율적이다.

포인터를 두개 만들어서 둘이 같아지면 루프를 빠져나오도록 만들면 된다.