두 개의 정수 n과 start가 주어졌을 때, 다음 조건을 만족하는 순열 p(0, 1, 2, ..., 2^n − 1)를 반환하는 것이 목표입니다.
- p[0] = start 여야 합니다.
- 인접한 두 원소 p[i]와 p[i+1]은 이진 표현에서 단 한 비트만 달라야 합니다.
- 첫 번째 원소 p[0]와 마지막 원소 p[2^n − 1] 역시 이진 표현에서 단 한 비트만 달라야 합니다. 즉, 수열이 '순환(circular)' 구조를 가져야 합니다.
예시
예를 들어 n = 2이고 start = 3이라면, 반환되는 배열은 [3, 2, 0, 1]입니다. 이를 이진수로 표현하면 [11, 10, 00, 01]이 되며, 인접한 값끼리 그리고 처음과 끝 값이 모두 한 비트씩만 차이 나는 것을 확인할 수 있습니다.
접근 방법
이 문제의 핵심은 그레이 코드(Gray Code)입니다. 그레이 코드는 인접한 두 수가 정확히 한 비트만 다른 특성을 가지며, i번째 그레이 코드 값은 i XOR (i >> 1)로 간단히 계산할 수 있습니다.
여기에 시작점 start를 반영하기 위해 전체 결과에 start를 XOR 연산하면 됩니다. XOR의 성질상 두 값이 한 비트만 다르면, 같은 값과 XOR한 후에도 여전히 한 비트만 다르게 유지되기 때문에 순환 순열의 조건이 그대로 보존됩니다.
따라서 해결 절차는 다음과 같습니다.
- 정답을 담을 배열 ans를 준비합니다.
- i를 0부터 2^n − 1까지 순회하면서 다음 값을 ans에 삽입합니다.
start XOR i XOR (i >> 1) - 순회가 끝나면 ans를 반환합니다.
이 방법의 시간 복잡도는 O(2^n), 공간 복잡도 역시 O(2^n)으로, 주어진 크기의 순열을 생성하는 데 최적화된 효율입니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> circularPermutation(int n, int start) {
vector <int> ans;
for(int i = 0 ; i < 1<<n; i++){
ans.push_back(start ^ i ^(i>>1));
}
return ans;
}
};
main(){
Solution ob;
print_vector(ob.circularPermutation(5,3));
}입력
5 3
출력
[3, 2, 0, 1, 5, 4, 6, 7, 15, 14, 12, 13, 9, 8, 10, 11, 27, 26, 24, 25, 29, 28, 30, 31, 23, 22, 20, 21, 17, 16, 18, 19]
코드 설명
circularPermutation 함수는 0부터 2^n − 1까지의 i에 대해 start ^ i ^ (i >> 1) 값을 계산하여 배열에 추가합니다. 위 실행 결과에서 n = 5, start = 3인 경우 총 32개의 원소가 생성되었으며, 각 인접 원소와 첫·마지막 원소 사이의 이진 표현 차이가 정확히 한 비트임을 알 수 있습니다.