C++에서 문자열을 팬그램으로 만드는 비용 계산하기

이 튜토리얼에서는 주어진 문자열을 팬그램(pangram)으로 만드는 데 드는 총비용을 계산하는 프로그램을 다룹니다.

팬그램이란?

팬그램은 영어 알파벳의 모든 문자(a부터 z까지)가 최소 한 번 이상 포함된 문자열을 의미합니다. 대표적인 예로 "The quick brown fox jumps over the lazy dog"가 있습니다.

문제 정의

정수 배열과 하나의 문자열이 주어집니다. 배열의 각 원소는 해당 위치의 알파벳을 문자열에 추가할 때 드는 비용을 나타냅니다. 즉, arr[0]은 'a'를 추가하는 비용, arr[1]은 'b'를 추가하는 비용입니다. 우리의 과제는 문자열에 빠져 있는 알파벳을 추가해 팬그램으로 완성하고, 이때 드는 총비용을 구하는 것입니다.

접근 방법

알고리즘은 다음과 같이 매우 간단합니다.

1. 크기 26의 불리언 배열을 선언하여 각 알파벳의 등장 여부를 추적합니다.
2. 주어진 문자열을 한 번 순회하며 등장한 문자를 표시합니다.
3. a부터 z까지 확인하면서 등장하지 않은 문자의 비용만 누적 합산합니다.
4. 누적된 총비용을 반환합니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
// 팬그램을 만드는
// 총비용 계산
int calc_cost(int arr[], string str) {
   int cost = 0;
   bool occurred[26] = { false };
   for (int i = 0; i < str.size(); i++)
      occurred[str[i] - 'a'] = true;
   for (int i = 0; i < 26; i++) {
      if (!occurred[i])
         cost += arr[i];
   }
   return cost;
}
int main(){
   int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 };
   string str = "abcdefghijklmopqrstuvwz";
   cout << calc_cost(arr, str);
   return 0;
}

출력 결과

63

코드 설명

예제에서 사용된 문자열 "abcdefghijklmopqrstuvwz"에는 n, x, y 세 개의 알파벳이 빠져 있습니다. 배열에서 각 문자의 추가 비용이 인덱스 값과 같으므로(n = 14, x = 24, y = 25), 총비용은 14 + 24 + 25 = 63이 됩니다.

calc_cost 함수는 먼저 occurred 배열을 통해 문자열에 이미 존재하는 알파벳을 기록한 뒤, 존재하지 않는 알파벳의 비용만 더하는 방식으로 동작합니다. 시간 복잡도는 문자열 길이 N에 대해 O(N)이며, 추가로 사용되는 공간은 크기 26의 고정 배열뿐이므로 공간 복잡도는 O(1)입니다.