C++의 아름다운 배열 II

두 개의 정수 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]에는 정확히 2개의 고유한 정수 1과 2가 있습니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ret 배열 정의
• i :=1, j :=n인 경우 i <=j
  인지 확인
  • k> 1이면
    • k가 홀수이면 i를 삽입하고 그렇지 않으면 j를 ret에 삽입
    • k가 홀수이면 i를 1 증가, 그렇지 않으면 j를 1 감소
    • k를 1 감소
  • 그렇지 않으면 res에 i를 삽입하고 i를 1만큼 증가
• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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, ]