C++에서 배열 요소를 오름차순·내림차순 번갈아 출력하는 방법

문제 소개

이번 문제에서는 숫자로 이루어진 배열이 하나 주어지고, 배열의 요소를 오름차순과 내림차순이 번갈아 등장하도록 순서대로 출력해야 합니다. 구체적인 규칙은 다음과 같습니다. 처음 두 개 요소는 오름차순으로 출력하고, 그다음 세 개 요소는 내림차순으로, 이후 네 개 요소는 다시 오름차순으로 출력합니다.

예시를 통해 문제를 더 쉽게 이해해 보겠습니다.

입력 : {1, 4, 0, 2, 7, 9, 3}
출력 : 0 1 9 7 4 2 3

설명 − 배열을 오름차순으로 정렬하면 0 1 2 3 4 7 9가 됩니다. 처음 두 요소는 0 1이고, 뒤쪽 세 요소는 9 7 4이며, 그다음 네 요소는 남은 2 3입니다(네 개를 출력해야 하지만 배열에 남은 요소가 두 개뿐입니다).

접근 방법

이 문제를 해결하려면 먼저 배열을 오름차순으로 정렬합니다. 이후 두 개의 포인터를 사용하는데, 하나는 배열 앞쪽에서 요소를 출력하기 위한 것이고, 다른 하나는 뒤쪽에서 요소를 출력하기 위한 것입니다. 또한 현재 출력을 앞쪽부터 해야 하는지 뒤쪽부터 해야 하는지 판단하기 위해 플래그(flag) 변수를 하나 함께 사용합니다.

알고리즘

1단계 : 배열의 요소들을 정렬한다.
2단계 : left = 0, right = n-1, flag = 2로 초기화한다.
3단계 : left가 right보다 작거나 같은 동안 반복한다.
4단계 : flag % 2 == 0이라면,
    4.1단계 : i = left부터 left + flag까지 반복하며 arr[i]를 출력한다.
    4.2단계 : left를 i로 갱신하고 flag를 1 증가시킨다.
5단계 : 그렇지 않다면,
    5.1단계 : i = right부터 right - flag까지 반복하며 arr[i]를 출력한다.
    5.2단계 : right를 i로 갱신하고 flag를 1 증가시킨다.
6단계 : 종료한다.

예제 코드

이제 위 알고리즘이 실제로 어떻게 동작하는지 확인할 수 있는 프로그램을 작성해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
void printAlternateSeq(int arr[], int n){
    sort(arr, arr + n);
    int left = 0, right = n - 1, flag = 2, i;
    while (left <= right) {
        if (flag % 2 == 0) {
            for (i = left; i < left + flag && i <= right; i++)
                cout << arr[i] << " ";
            left = i;
        } else {
            for (i = right; i > right - flag && i >= left; i--)
                cout << arr[i] << " ";
            right = i;
        }
        flag++;
    }
}
int main(){
    int n = 6;
    int arr[] = {23, 45, 78, 32, 89, 10};
    printAlternateSeq(arr, n);
    return 0;
}

출력 결과

10 23 89 78 45 32

시간 복잡도 분석

배열을 정렬하는 데 O(n log n)의 시간이 걸리고, 정렬된 배열의 각 요소는 출력 과정에서 정확히 한 번씩만 처리되므로 전체 시간 복잡도는 O(n log n)입니다. 추가로 사용되는 메모리는 포인터 두 개와 플래그 변수뿐이므로 공간 복잡도는 O(1)입니다.