C++로 배열에서 K번째 홀수 찾는 방법 완벽 가이드

이 튜토리얼에서는 주어진 배열에서 k번째 홀수를 찾는 프로그램을 C++로 작성해 보겠습니다. 배열을 한 번만 순회하면서 간단하게 해결할 수 있는 문제입니다.

문제 해결 접근 방식

문제를 해결하는 단계는 다음과 같습니다.

• 배열과 k 값을 초기화합니다.
• 배열을 처음부터 끝까지 순회합니다.
  • 현재 요소가 홀수라면 k의 값을 1 감소시킵니다.
  • k가 0이 되면 해당 요소가 바로 k번째 홀수이므로 이를 반환합니다.
• 배열을 모두 순회했는데도 k번째 홀수를 찾지 못했다면 -1을 반환합니다.

예제 코드

위 알고리즘을 구현한 전체 코드를 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;

int findKthOddNumber(int arr[], int n, int k) {
    for (int i = 0; i < n; i++) {
        if (arr[i] % 2 == 1) {
            k--;
        }
        if (k == 0) {
            return arr[i];
        }
    }
    return -1;
}

int main() {
    int arr[] = { 4, 5, 22, 1, 55 }, k = 3;
    cout << findKthOddNumber(arr, 5, k) << endl;
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

55

코드 설명

예제 배열 {4, 5, 22, 1, 55}에서 홀수는 차례대로 5, 1, 55입니다. 따라서 k가 3일 때 세 번째 홀수인 55가 반환됩니다.

이 알고리즘의 시간 복잡도는 O(n)으로, 배열을 한 번만 순회하기 때문에 매우 효율적입니다. 공간 복잡도 역시 추가 메모리가 필요 없으므로 O(1)입니다.

마무리

지금까지 C++을 사용해 배열에서 k번째 홀수를 찾는 방법을 알아보았습니다. 코드에 대해 궁금한 점이 있다면 댓글로 남겨주세요.