C++의 아름다운 배열

N의 일부 고정 값에 대해 배열 A는 정수 1, 2, ..., N의 순열일 때 아름답습니다. 다음과 같이 −

• 모든 i

N이 있다고 가정하고 아름다운 배열 A를 찾아야 합니다.

따라서 입력이 5와 같으면 출력은 [3,1,2,5,4]

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

• ret라는 배열 하나를 만들고 ret에 1을 삽입

• ret 의 크기

  • 배열 임시 만들기

  • 범위 0에서 ret – 1까지의 i에 대해

    • ret[i] * 2 – 1 <=N이면 임시 배열에 ret[i] * 2 – 1을 삽입합니다.

  • 범위 0에서 ret – 1까지의 i에 대해

  • ret[i] * 2 <=N이면 임시 배열에 ret[i] * 2를 삽입합니다.

  • set ret :=temp

• 리턴 렛

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

예시

#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> beautifulArray(int N) {
      vector <int> ret;
      ret.push_back(1);
      while(ret.size() < N){
         vector <int> temp;
         for(int i = 0; i < ret.size(); i++){
            if(ret[i] * 2 - 1 <= N) temp.push_back(ret[i] * 2 - 1);
         }
         for(int i = 0; i < ret.size(); i++){
            if(ret[i] * 2 <= N)temp.push_back(ret[i] * 2 );
         }
         ret = temp;
      }
      return ret;
   }
};
main(){
   Solution ob;
   print_vector(ob.beautifulArray(6));
}

입력

5

출력

[1,5,3,2,4]