[C++/배열,스캔] 오르락 내리락

• n 개의 정수를 배열 A에 저장한다. A의 값을 재 배치해서 새로운 배열 B를 만드는 데, B[0] <= B[1] >= B[2] <= B[3] >= B[4] <= ... 이 만족하도록 B를 만들어라.
  • 2 <= n <= 100,000
  • 당연히, 정답은 유일하지 않다.
• solve 함수는 A를 입력으로 받아 위의 조건을 만족하는 B를 리턴한다. 이 배열 B가 조건에 맞는지 검사하는 check 함수를 호출해 그 결과를 출력한다. (check 함수와 입력 처리 코드는 수정하지 않는다)
• 주석 필요 : 알고리즘의 수행시간을 분석하고 Big-O로 표기하라.
• 예 : A = [1,3,4,9,2] 인 경우에 B = [1,4,3,9,2]가 답이 될 수 있고, B = [1,3,2,9,4]도 답이다.

---

배열스캔 구현 문제입니다. 문제에 접근하면서 어떠한 자료구조를 써야할지를 고민했습니다. 하지만 손으로 직접 재 배치를 하다보니 반복문 만으로도 문제가 해결이 가능하다는 것을 알았습니다.

 

짝수인덱스 (ex 0,2,4,...) 는 항상 양 옆보다 크기가 작거나 같아야하고

홀수인덱스 (ex 1,3,5,...) 는 항상 양 옆보다 크거나 같아야 합니다.

 

• i가 짝수인경우
  • A[i]가 A[i+1]보다 항상 작아야합니다. 하지만 A[i+1]보다 A[i]가 큰경우 두 수의 자리를 바꿔줍니다.
• i가 홀수인경우
  
  • 반대로 A[i]가 A[i+1]보다 항상 커야합니다. 하지만 반대인 경우 두 수의 자리를 바꿔줍니다.
• A[0] = 8, A[1] = 3, A[2] = 5 인경우는
  • A[0]과 A[1]을 바꿔 [3,8,5] 가됩니다. 그리고 A[1]과 A[2]를 비교해 A[1]이 큰 경우이기때문에 그대로 냅둡니다.

전체 소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <stdio.h>
using namespace std;

const int MAX = 100001;
int idx = 0;

bool check(int b[]);
int* solve(int a[]);

int* solve(int a[])
{
    int temp;
    if(a[0]>=a[1])
    {
        temp = a[0];
        a[0] = a[1];
        a[1] = temp;
    }

//1 2 3 4 5
    for(int i=1;i<idx-1;i++)
    {
        if(i%2==1) //홀수 번째 인덱스는 앞 뒤에 비해 커야함
        {
            if(a[i]<a[i+1])
            {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
        }
        else if(i%2==0) //짝수 번째 인덱스는 앞 뒤에 비해 작아야함
        {
           if(a[i]>a[i+1])
           {
                temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
           }
        }
    }
    return a;
}

bool check(int b[])
{
    if(!(b[0]<=b[1]))
        return false;
    for(int i=1;i<idx-1;i++)
    {
        if(i%2==1&&!(b[i]>=b[i+1]))
            return false;
        if(i%2==0&&!(b[i]<=b[i+1]))
            return false;
    }
    return true;
}
int main()
{
    int n;
    int A[MAX];
    do{
        cin>>n;
        A[idx++] = n;
    }while(getc(stdin)==' ');

    int* B = solve(A);
	
	
    bool flag = check(B);
    if(flag == 0)
        cout<<"False"<<endl;
    else
        cout<<"True"<<endl;
    return 0;
}


/*
O(n)으로 해결하였습니다. 반복문을 통해 idx-1까지 홀수번째 인덱스는 앞 뒤 숫자보다 항상 크거나 같아야하고
짝수번째 인덱스는 앞 뒤 숫자보다 항상 작거나 같아야합니다. 해당 조건이 아니라면 A[i]와 A[i+1] 자리를 바꾸는 방식으로
반복문을 통해 구현하였습니다. solve가 끝나면 배열의 포인터를 return하여 B배열의 시작점으로 구성하였고 해당 B 포인터가
다시 check함수의 매개변수로 넘어가 check함수를 실행해  True와 False를 출력합니다.

반복문을 solve에서 IDX(n)-1 번째까지 반복문을 실행하기 때문에 시간복잡도는 O(n)이라고 할 수 있습니다.


*/