Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 8의 배수이면서 3의 배수가 아닌 부분 문자열 개수 구하기

문제 개요

0부터 9 사이의 숫자로 이루어진 문자열이 주어집니다. 이 문제의 목표는 8로 나누어떨어지면서 3으로는 나누어떨어지지 않는 부분 문자열의 개수를 계산하는 것입니다. 문제를 두 단계로 나누어 한 단계씩 코드를 작성하며 차근차근 해결해 보겠습니다.

입력 예시 1

str = "80"

출력

2

입력 예시 2

str = "7675636788"

출력

15

해결 접근 방식

이 문제를 효율적으로 풀기 위해서는 두 가지 수학적 성질을 활용합니다.

  • 8의 배수 판별: 어떤 수가 8로 나누어떨어지는지 확인하려면 마지막 3자리 숫자만 검사하면 됩니다.

  • 3의 배수 판별: 각 자리 숫자의 합이 3으로 나누어떨어지면 그 수 역시 3의 배수입니다.

먼저 문자열의 접두사 합(prefix sum)을 저장하여, 각 위치까지의 자릿수 합을 3으로 나눈 나머지가 0, 1, 2 중 무엇인지 기록해 둡니다. 그다음 문자열의 모든 위치 i를 순회하면서 다음 작업을 수행합니다.

  1. 위치 i에서 끝나며 8로 나누어떨어지는 부분 문자열의 개수를 셉니다.
  2. 여기서 같은 범위 안에서 3으로도 나누어떨어지는 부분 문자열의 개수를 빼줍니다.

이를 위해 크기 |S| × 3의 2차원 배열 dp[i][j]를 정의합니다(|S|는 문자열의 길이). dp[i][j]는 인덱스 i부터 0까지 거슬러 올라가며 만들 수 있는 부분 문자열 중 자릿수 합을 3으로 나눈 나머지가 j(0 ≤ j ≤ 2)인 것의 개수를 의미합니다.

이후 문자열을 순회하며 한 자리, 두 자리, 세 자리 숫자가 각각 8의 배수인지 확인합니다.

  • 한 자리 숫자: 해당 인덱스의 문자가 '8'인지 확인합니다.

  • 두 자리 숫자: 앞 문자와 현재 문자로 만든 두 자리 수가 8로 나누어떨어지는지 확인하고, 3의 배수인 경우는 제외합니다.

  • 세 자리 숫자: 세 자리 수가 8로 나누어떨어지면 가능한 시작 위치의 개수를 정답에 더한 뒤, DP 배열을 이용해 3의 배수에 해당하는 경우를 차감합니다.

세 자리 수가 8의 배수라면 최대 (i-2)개의 부분 문자열이 존재할 수 있습니다. 다만 이중에는 3의 배수인 것도 포함되어 있으므로, DP 배열을 활용해 이를 정확히 걸러내야 합니다.

C++ 구현 예제

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

#define MAX 1000
int count (char s[], int len) {
    int cur = 0,
    dig = 0;
    int sum[MAX], dp[MAX][3];
    memset (sum, 0, sizeof (sum));
    memset (dp, 0, sizeof (dp));
    dp[0][0] = 1;
    for (int i = 1; i <= len; i++) {
        dig = int (s[i - 1]) - 48;
        cur += dig;
        cur %= 3;
        sum[i] = cur;
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = dp[i - 1][1];
        dp[i][2] = dp[i - 1][2];
        dp[i][sum[i]]++;
    }
    int ans = 0, dprev = 0, value = 0, dprev2 = 0;
    for (int i = 1; i <= len; i++) {
        dig = int (s[i - 1]) - 48;
        if (dig == 8) ans++;
        if (i - 2 >= 0) {
            dprev = int (s[i - 2]) - 48;
            value = dprev * 10 + dig;
            if ((value % 8 == 0) && (value % 3 != 0)) ans++;
        }
        // 세 자리 숫자 처리
        if (i - 3 >= 0){
            dprev2 = int (s[i - 3]) - 48;
            dprev = int (s[i - 2]) - 48;
            value = dprev2 * 100 + dprev * 10 + dig;
            if (value % 8 != 0) continue;
                ans += (i - 2);
            ans -= (dp[i - 3][sum[i]]);
        }
    }
    return ans;
}
int main () {
    char str[] = "7675636788";
    int len = strlen (str);
    cout << count (str, len) << endl;
    return 0;
}

실행 결과

4

마무리

이번 글에서는 8로 나누어떨어지지만 3으로는 나누어떨어지지 않는 부분 문자열의 개수를 구하는 방법과 이를 구현한 C++ 코드를 살펴보았습니다. 동일한 로직은 Java, Python 등 다른 프로그래밍 언어로도 손쉽게 옮겨 작성할 수 있습니다. 문제를 "8의 배수 찾기"와 "3의 배수 제외하기"라는 두 단계로 나누어 접근하면 훨씬 직관적이고 명확하게 해결할 수 있다는 점을 기억해 두세요.