[5. 배열] 5.1 네덜란드 국기 문제

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

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

---

[5. 배열] 단원의 기본 셋팅은 다음과 같다.

Q5.h

main에서 vector형태로 출력하기위한 기본셋팅

네덜란드 국기 문제.h

 

---

Q 5.1 네덜란드 국기 문제

퀵 정렬 알고리즘은 다음과 같은 과정을 재귀적으로 반복한다.
원소를 선택후 이보자 작거나 같은 그룹은 왼쪽, 이보다 큰 그룹은 오른쪽으로 나오도록 재배치한다.

네덜란드 국기의 형태가 이 세가지 그룹처럼 서로 다른 세가지 색깔의 묶음으로 구성되어 있기 때문에 네덜란드 국기 나누기 라고 부른다.

이때 배열 A와 인덱스 i가 주어졌을 때, A[i](피벗) 보다 작은 원소, 피벗과 같은원소, 피벗보다 큰 원소 순으로 원소를 재배열하는 프로그램을 작성하시오.

---

배열의 길이를 n이라고 할때 O(n)의 공간을 추가로 사용한다면 문제는 간단하다.
피벗보다 작은 원소, 같은 원소, 큰 원소를 차례대로 넣어주면 시간복잡도 O(n)으로 간단하게 해결된다.

그러나 추가공간을 사용하지않는 방향으로 문제를 풀면 다음과 같다.

공간복잡도 O(1), 시간복잡도 O(n²)

enum에 의해 [kRed=1, kWhite=2, kBlue=3]

결과

 

위의 방법은 시간복잡도적으로 효율적이지 못하다. 그래서 단일 패스를 통해 피벗보다 작은 원소를 모두 앞으로 옮긴뒤, 피벗보다 큰 원소를 오른쪽으로 옮기는 방법을 사용하면 다음과 같다.

공간복잡도 O(n), 시간복잡도O(1)

결과