C언어로 N의 가장 큰 홀수 자릿수와 곱 구하기

주어진 숫자 N이 있을 때, N을 그 숫자에서 가장 큰 홀수 자릿수와 곱한 값을 구해야 합니다. 만약 숫자에 홀수 자릿수가 하나도 없다면 -1을 출력합니다.

예를 들어 N을 "153"으로 초기화했다고 가정해 봅시다. 이 숫자에서 가장 큰 홀수 자릿수는 5이므로 결과는 153 × 5 = 765가 됩니다. 반면 246처럼 홀수 자릿수가 전혀 포함되지 않은 숫자라면 출력은 -1이 되어야 합니다.

입력 및 출력 예시

• 입력: N = 198
  출력: 1782
  설명: 198 × 9 = 1782
• 입력: N = 15382
  출력: 76910
  설명: 15382 × 5 = 76910

문제 해결 접근 방식

1. 입력 N을 받습니다.
2. 모든 자릿수를 하나씩 탐색하며 홀수 자릿수를 찾습니다.
3. 그중 가장 큰 홀수 자릿수를 구합니다.
4. 가장 큰 홀수 자릿수와 원래 숫자 N을 곱합니다.
5. 홀수 자릿수가 존재하지 않으면 결과를 -1로 갱신합니다.
6. 최종 결과를 반환합니다.

알고리즘

시작
함수 int largestodd(int n)
    단계 1 → large를 -1로 선언 및 초기화
    단계 2 → n > 0인 동안 반복
        digit을 n % 10으로 설정
        만약 digit % 2 == 1 이고 digit > large라면,
            large를 digit으로 설정
        n을 n / 10으로 설정
    단계 3 → large 반환
함수 int findproduct(int n)
    단계 1 → largestodd(n)의 반환값으로 large를 선언 및 초기화
    단계 2 → 만약 large == -1이라면,
        -1 반환
    단계 3 → (n * large) 반환
함수 int main()
    단계 1 → n을 15637로 초기화
    findproduct(n) 호출 결과를 출력
종료

C 코드 구현 예제

#include <stdio.h>

int largestodd(int n){
    // 모든 자릿수가 짝수라면 -1을 반환
    int large = -1;
    while (n > 0) {
        // 마지막 자릿수부터 확인
        int digit = n % 10;
        // 현재 자릿수가 홀수이고 large보다 크다면
        if (digit % 2 == 1 && digit > large)
            large = digit;
        n = n / 10;
    }
    // n의 최대 홀수 자릿수를 반환
    return large;
}

int findproduct(int n){
    int large = largestodd(n);
    // n에 홀수 자릿수가 없는 경우
    if (large == -1)
        return -1;
    // n과 가장 큰 홀수 자릿수의 곱을 반환
    return (n * large);
}

int main(){
    int n = 15637;
    printf("%d\n", findproduct(n));
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

109459

복잡도 분석

이 알고리즘은 숫자의 각 자릿수를 한 번씩만 확인하므로 시간 복잡도는 자릿수 개수에 비례하는 O(log₁₀N)입니다. 또한 별도의 저장 공간을 사용하지 않으므로 공간 복잡도 역시 O(1)로 매우 효율적입니다.