두 개의 정수 n과 k가 주어졌을 때, 1부터 n까지 범위에 속하는 서로 다른 양의 정수 n개로 이루어진 배열을 만들어야 합니다. 단, 이 배열은 다음 규칙을 만족해야 합니다.
만들어진 배열이 [a1, a2, a3, …, an]일 때, 인접한 두 원소의 절댓값 차이로 이루어진 목록 [|a1 − a2|, |a2 − a3|, |a3 − a4|, …, |an−1 − an|]에는 정확히 k개의 고유한 정수가 존재해야 합니다. 조건을 만족하는 답이 여러 개라면 그중 어떤 것을 출력해도 무방합니다.
예를 들어 입력이 n = 3, k = 2라면 결과는 [1, 3, 2]가 될 수 있습니다. [1, 3, 2]는 1부터 3 사이의 서로 다른 세 양의 정수를 포함하고 있으며, 인접 원소 간의 차이 목록인 [2, 1]은 정확히 1과 2라는 두 개의 고유한 값을 가집니다.
해결 방법
이 문제는 투 포인터(two pointer) 기법으로 해결할 수 있습니다. 핵심 아이디어는 가장 작은 수(i)와 가장 큰 수(j)를 번갈아 배치하는 것입니다. 작은 값과 큰 값을 교차로 선택하면 인접 원소 간의 차이가 매번 달라지므로, 원하는 개수(k)만큼의 고유한 차잇값을 만들 수 있습니다. k개의 차잇값을 모두 확보한 뒤에는 남은 숫자들을 오름차순으로 이어 붙이면 되는데, 이 과정에서는 새로운 차잇값이 생기지 않습니다.
구체적인 알고리즘은 다음과 같습니다.
- 결과를 저장할 배열 ret을 선언합니다.
- i := 1, j := n으로 초기화한 후, i <= j인 동안 반복합니다.
- k > 1인 경우:
- k가 홀수면 i를, 짝수면 j를 ret에 삽입합니다.
- k가 홀수면 i를 1 증가시키고, 짝수면 j를 1 감소시킵니다.
- k를 1 감소시킵니다.
- 그 외의 경우(k <= 1)에는 i를 ret에 삽입하고 i를 1 증가시킵니다.
- 반복이 종료되면 ret을 반환합니다.
다음 예제 코드를 살펴보면 더 쉽게 이해할 수 있습니다.
예제 코드(C++)
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<int> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> constructArray(int n, int k) {
vector <int> ret;
for(int i = 1, j = n; i <= j; ){
if(k > 1){
ret.push_back(k % 2 ? i : j);
if(k % 2 == 1){
i++;
}else j--;
k--;
} else {
ret.push_back(i++);
}
}
return ret;
}
};
main(){
Solution ob;
print_vector(ob.constructArray(3, 2));
}입력
3 2
출력
[3, 1, 2]
실행 결과인 [3, 1, 2] 역시 유효한 답입니다. 이 배열의 인접 원소 차이는 [2, 1]로, 정확히 2개의 고유한 값을 가지므로 문제의 조건을 충족합니다.