정수 배열의 홀짝 조건부 정렬

주어진 정수 시퀀스를 특정 규칙에 따라 재정렬하는 문제에 대해 살펴보겠습니다. 이 문제에서는 10개의 정수를 입력받아 다음과 같은 세 가지 주요 조건에 맞춰 정렬해야 합니다.

  1. 홀수는 배열의 앞쪽에 배치하고, 짝수는 뒤쪽에 배치합니다.
  2. 홀수들 사이에서는 내림차순(큰 수부터 작은 수 순서)으로 정렬합니다.
  3. 짝수들 사이에서는 오름차순(작은 수부터 큰 수 순서)으로 정렬합니다.

입력 형식

한 줄에 10개의 정수가 공백으로 구분되어 입력됩니다. 각 정수의 범위는 0 이상 30000 이하입니다.

입력 예시:

4 7 3 13 11 12 0 47 34 98

출력 형식

정렬 요구사항에 따라 재정렬된 10개의 정수를 한 줄에 공백으로 구분하여 출력합니다.

출력 예시:

47 13 11 7 3 0 4 12 34 98

문제 해결 전략

이러한 복합적인 정렬 조건을 처리하기 위한 효과적인 방법은 다음과 같습니다.

  1. 홀수와 짝수 분리: 입력받은 정수들을 홀수 그룹과 짝수 그룹으로 먼저 나눕니다.
  2. 각 그룹별 정렬:
    • 홀수 그룹은 내림차순으로 정렬합니다.
    • 짝수 그룹은 오름차순으로 정렬합니다.
  3. 그룹 병합: 정렬된 홀수 그룹을 먼저 배치하고, 그 뒤에 정렬된 짝수 그룹을 이어 붙여 최종 결과 시퀀스를 만듭니다.

C++ 구현 예시

위 전략을 바탕으로 C++ 코드를 작성하면 다음과 같습니다. std::vector를 사용하여 가변적인 크기의 그룹을 관리하고, std::sort 함수를 활용하여 각 그룹을 효율적으로 정렬합니다.

#include <iostream>     // 표준 입출력을 위해
#include <vector>       // 동적 배열(vector) 사용을 위해
#include <algorithm>    // std::sort, std::greater 등의 정렬 함수를 위해
#include <functional>   // std::greater를 위해 (std::algorithm에 포함될 수도 있음)

int main() {
    // 입출력 성능 최적화
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 홀수와 짝수를 저장할 벡터 선언
    std::vector<int> oddNumbers;
    std::vector<int> evenNumbers;

    // 10개의 정수를 입력받아 홀수 또는 짝수 벡터에 추가
    for (int i = 0; i < 10; ++i) {
        int currentNum;
        std::cin >> currentNum;
        if (currentNum % 2 != 0) { // 홀수이면
            oddNumbers.push_back(currentNum);
        } else { // 짝수이면
            evenNumbers.push_back(currentNum);
        }
    }

    // 홀수 벡터를 내림차순으로 정렬 (std::greater<int>는 내림차순 비교자)
    std::sort(oddNumbers.begin(), oddNumbers.end(), std::greater<int>());

    // 짝수 벡터를 오름차순으로 정렬 (std::sort의 기본 동작은 오름차순)
    std::sort(evenNumbers.begin(), evenNumbers.end());

    // 정렬된 홀수와 짝수 벡터를 하나의 최종 시퀀스로 병합
    std::vector<int> finalSequence;
    finalSequence.reserve(oddNumbers.size() + evenNumbers.size()); // 메모리 사전 할당으로 효율 증가
    finalSequence.insert(finalSequence.end(), oddNumbers.begin(), oddNumbers.end());
    finalSequence.insert(finalSequence.end(), evenNumbers.begin(), evenNumbers.end());

    // 최종 정렬된 시퀀스를 출력 (마지막 숫자 뒤에 공백 없음)
    for (size_t i = 0; i < finalSequence.size(); ++i) {
        std::cout << finalSequence[i] << (i == finalSequence.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;

    return 0;
}

코드 설명

  • #include <iostream>, <vector>, <algorithm>, <functional>: 필요한 표준 라이브러리를 포함합니다. 각각 입출력, 동적 배열(std::vector), 정렬 알고리즘(std::sort), 그리고 비교 함수 객체(std::greater)를 제공합니다.
  • std::ios_base::sync_with_stdio(false); std::cin.tie(NULL);: C++ 표준 스트림과 C 표준 스트림의 동기화를 해제하고, cin과 cout의 연결을 끊어 입출력 속도를 향상시킵니다. 경쟁 프로그래밍 환경에서 자주 사용되는 최적화 기법입니다.
  • std::vector<int> oddNumbers;, std::vector<int> evenNumbers;: 홀수와 짝수를 각각 저장할 두 개의 std::vector를 선언합니다. std::vector는 배열과 유사하지만, 크기가 동적으로 조절될 수 있어 편리합니다.
  • 입력 및 분리 루프: 
    for (int i = 0; i < 10; ++i) {
        int currentNum;
        std::cin >> currentNum;
        if (currentNum % 2 != 0) { // 홀수 판별
            oddNumbers.push_back(currentNum);
        } else { // 짝수 판별
            evenNumbers.push_back(currentNum);
        }
    }
    10번 반복하여 정수를 입력받고, currentNum % 2 != 0 조건으로 홀수인지 짝수인지 판별합니다. 홀수이면 oddNumbers 벡터에, 짝수이면 evenNumbers 벡터에 추가합니다. push_back()은 벡터의 끝에 요소를 추가하는 메서드입니다.
  • 홀수 정렬: 
    std::sort(oddNumbers.begin(), oddNumbers.end(), std::greater<int>());
    std::sort 함수는 세 번째 인자로 비교 함수 객체를 받을 수 있습니다. std::greater<int>()는 '더 크다'는 의미의 비교자(comparator)로, 이를 사용하면 oddNumbers 벡터의 요소들이 내림차순으로 정렬됩니다.
  • 짝수 정렬: 
    std::sort(evenNumbers.begin(), evenNumbers.end());
    std::sort 함수에 세 번째 인자를 전달하지 않으면 기본적으로 오름차순으로 정렬됩니다. 따라서 evenNumbers는 가장 작은 수부터 큰 수 순서로 정렬됩니다.
  • 최종 시퀀스 병합: 
    std::vector<int> finalSequence;
    finalSequence.reserve(oddNumbers.size() + evenNumbers.size());
    finalSequence.insert(finalSequence.end(), oddNumbers.begin(), oddNumbers.end());
    finalSequence.insert(finalSequence.end(), evenNumbers.begin(), evenNumbers.end());
    정렬된 oddNumbers와 evenNumbers를 합쳐 최종 결과를 담을 finalSequence 벡터를 만듭니다. reserve()는 벡터가 필요한 만큼의 메모리를 미리 할당하게 하여 insert() 과정에서 발생할 수 있는 잦은 재할당을 방지하여 성능을 향상시킵니다. insert() 메서드는 다른 범위의 요소들을 삽입하는 데 사용됩니다. 먼저 모든 홀수를 삽입한 후, 이어서 모든 짝수를 삽입합니다.
  • 결과 출력: 
    for (size_t i = 0; i < finalSequence.size(); ++i) {
        std::cout << finalSequence[i] << (i == finalSequence.size() - 1 ? "" : " ");
    }
    std::cout << std::endl;
    finalSequence의 모든 요소를 반복하면서 출력합니다. 각 숫자 뒤에는 공백을 추가하지만, finalSequence.size() - 1이 마지막 인덱스와 같을 경우, 즉 마지막 숫자 뒤에는 공백을 추가하지 않도록 조건부 삼항 연산자를 사용합니다. std::endl은 줄바꿈 문자를 출력하고 출력 스트림을 비웁니다.

이 방법은 문제의 요구사항을 명확하게 분리하여 처리함으로써 코드의 가독성을 높이고, 각 단계별로 직관적인 정렬 로직을 적용할 수 있습니다.

태그: C++ algorithm sorting vector std::sort

8월 4일 11:33에 게시됨

인기 태그

©2026 괴물 클럽