[5. 배열] 5.8 대체 연산

[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다. 

문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.

---

 

---

Q 5.8 대체 연산

n개의 숫자를 원소로 가지는 배열 A를
B[0] <= B[1] >= B[2] <= B[3] >= B[4] <= B[5] >= ... 와 같은 특징을 가지도록, 새로운 배열 B에 재배치하라.

---

간단한 방법은 배열A를 정렬한다음 (A[1], A[2])와 (A[3],A[4])를 서로 교환하는 방식으로 만드는 방법이있다. 이때 시간 복잡도는 O(n log n) 이다.
그러나 정렬은 하지 않고 가능하다. i가 짝수이며, A[i]>A[i+1] 이거나, 홀수이며 A[i] < A[i+1] 일때 A[i]와 A[i+1]를 교환하면 해결된다.

해당 코드와 결과는 다음과 같다.

시간복잡도 O(n)

main

결과