정수 변수 N과 K가 주어졌을 때, 먼저 1부터 N까지의 순열을 계산한 뒤, 모든 원소가 원래 위치에서 정확히 K 거리만큼 떨어지도록 순열을 재배열하는 것이 이 글의 목표입니다.
입출력 시나리오 살펴보기
입력 − int n = 20, int k = 2
출력 − 처음 N개의 숫자를 K 거리만큼 재배열한 결과: 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18
설명 − 정수 N(=20)과 K(=2)가 주어집니다. 먼저 1부터 20까지의 순열을 계산한 후, 각 원소가 원래 자리에서 정확히 2칸씩 떨어지도록 배치합니다. 예를 들어 1은 세 번째 위치로, 2는 네 번째 위치로 이동하며, 이러한 패턴이 수열 전체에 걸쳐 반복됩니다.
입력 − int n = 10, int k = 3
출력 − Not Possible (재배열 불가능)
설명 − 정수 N(=10)과 K(=3)가 주어집니다. 1부터 10까지의 순열을 계산하지만, N을 2×K로 나눈 나머지가 0이 아니면(10 ÷ 6의 나머지는 4) 조건을 만족하는 재배열이 존재하지 않으므로 "Not Possible"을 출력합니다.
핵심 아이디어
모든 원소를 정확히 K 거리만큼 이동시키려면 수열을 크기가 2×K인 블록으로 나누고, 각 블록 안에서 앞쪽 K개와 뒤쪽 K개를 서로 맞바꾸면 됩니다. 이렇게 하면 블록 내 모든 원소가 정확히 K칸씩 이동합니다. 따라서 N이 2×K로 나누어떨어지지 않으면 남는 원소를 처리할 수 없어 재배열이 불가능합니다.
프로그램에 사용된 접근 방식
정수형 값 N과 K를 입력받습니다.
N과 K를 매개변수로 전달하여 Rearrangement(int n, int k) 함수를 호출합니다.
함수 내부에서는 다음과 같이 동작합니다.
정수형 변수 temp를 선언하고 n % (2 * k) 값으로 초기화합니다.
크기가 n + 1인 정수형 배열 ptr을 선언합니다.
k가 0이라면 거리 제약이 없으므로 1부터 n까지의 숫자를 그대로 출력하고 함수를 종료합니다.
temp가 0이 아니라면 재배열이 불가능하므로 "Not Possible"을 출력합니다.
반복문을 사용해 ptr[i]에 i를 대입하여 초기 순열을 구성합니다.
i를 1부터 n까지 2 * k씩 증가시키는 외부 반복문 안에서, j를 1부터 k까지 증가시키는 내부 반복문을 실행하며 swap 함수를 호출해 ptr[i + j - 1]과 ptr[k + i + j - 1]의 값을 교환합니다. 이 과정이 크기가 k인 인접한 두 블록을 맞바꾸는 역할을 합니다.
마지막으로 1부터 n까지 반복하면서 ptr[i]를 차례대로 출력합니다.
결과를 화면에 출력합니다.
예제
#include <bits/stdc++.h>
using namespace std;
void Rearrangement(int n, int k){
int temp = n % (2 * k);
int ptr[n + 1];
if(k == 0){
for(int i = 1; i <= n; i++){
cout << i << " ";
}
return;
}
if(temp != 0){
cout<<"Not Possible";
return;
}
for(int i = 1; i <= n; i++){
ptr[i] = i;
}
for(int i = 1; i <= n; i += 2 * k){
for(int j = 1; j <= k; j++){
swap(ptr[i + j - 1], ptr[k + i + j - 1]);
}
}
for(int i = 1; i <= n; i++){
cout << ptr[i] << " ";
}
}
int main(){
int n = 20;
int k = 2;
cout<<"Rearrangement of first N numbers to make them at K distance is: ";
Rearrangement(n, k);
return 0;
}출력
위 코드를 실행하면 다음과 같은 결과가 생성됩니다.
Rearrangement of first N numbers to make them at K distance is: 3 4 1 2 7 8 5 6 11 12 9 10 15 16 13 14 19 20 17 18