[5. 배열] 5.10 배열 안의 원소로 순열 구하기
[해당 문제는 266가지 문제로 정복하는 코딩 인터뷰]
책의 내용의 문제와 풀이를 베이스로 공부하는 내용이다.
문제를 풀기전에 단순하게 문제를 푸는것이 목적이 아닌
시간복잡도와 공간복잡도의 관계를 계산하며,
자료구조의 이해도와 실력을 향상하는데 목적이 있다.
Q 5.10 배열 안의 원소로 순열 구하기
배열에 주어진 숫자대로 순열을 재배치 하는 프로그램을 작성하라.
ex) 배열 P = <2, 0, 1, 3>안의 순열을 배열 A = <a, b, c, d>에 적용하면 <b, c, a, d>가 된다.
0,1,2,3 순서대로 배치되어야함 그래서 b,c,a,d이다.
추가 공간을 사용할 수 있다면 간단하게 문제를 풀 수 있다.
주어진 배열A와 길이가 같은 새로운 배열B를 사용하여 위치 i에 대하여 B[P[i]] = A[i] 로 할당한 뒤
B의 결과를 A로 복사하면 시간 복잡도 O(n), 공간 복잡도 O(n)으로 간단하게 해결할 수 있다.
그러나 추가 공간을 사용하지 않고 문제를 풀어보자.
예를 들어
A = <a,b,c,d>, P = <2,0,1,3> 일때 i=0일때를 확인하고 교환한다.
A = <c,b,a,d>, P = <1,0,2,3> 가 되며 i=0일때를 또 확인하고 교환한다.
A = <b,c,a,d>, P = <0,1,2,3> 가 되며 P[i] == i 인지 확인하는 방법으로 재배치 되었는지 확인한다.
코드와 결과는 다음과 같다.
해당 코드의 시간 복잡도와 공간 복잡도는 처음의 방법과 동일하나 추가 메모리를 사용하지 않는다.
