숫자 num이 입력으로 주어졌을 때, 길이가 num이면서 모든 인접한 두 문자의 ASCII 값 차이가 정확히 1이 되는 문자열의 개수를 세는 것이 목표입니다.
예를 들어 num이 2라면 가능한 문자열은 "ab", "ba", "bc", "cb", ……, "yz", "zy"와 같습니다.
예시로 이해하기
입력 − num=3
출력 − 인접 문자의 차이가 1인 문자열의 개수: 98
설명 − "abc", "aba", "cde", …, "xyx", "zyz", "xyz" 등의 문자열이 조건을 만족합니다.
입력 − num=2
출력 − 인접 문자의 차이가 1인 문자열의 개수: 50
설명 − "ab", "ba", "cd", …, "xy", "zy", "yz" 등의 문자열이 조건을 만족합니다.
문제 해결 접근 방식
먼저 길이가 2인 경우를 살펴보겠습니다.
- 'a'로 시작하는 문자열: "ab"
- 'b'로 시작하는 문자열: "ba", "bc"
- 'c'로 시작하는 문자열: "cd", "cb" … 등
이 규칙을 길이 n으로 일반화하면 다음과 같습니다.
- 'a'로 시작하는 길이 n 문자열의 수 = 'b'로 시작하는 길이 n−1 문자열의 경우의 수
- 'b'로 시작하는 길이 n 문자열의 수 = 'a' 또는 'c'로 시작하는 길이 n−1 문자열의 경우의 수
- 'c'로 시작하는 길이 n 문자열의 수 = 'b' 또는 'd'로 시작하는 길이 n−1 문자열의 경우의 수
즉, 각 위치에서 다음에 올 수 있는 문자는 현재 문자보다 ASCII 값이 1 크거나 1 작은 문자뿐입니다. 이러한 중복되는 부분 문제 구조 때문에 이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다.
2차원 배열 arr[num+1][27]을 선언하고, arr[i][j]에는 알파벳 번호 j(0='a', 1='b', …, 25='z')로 시작하는 길이 i의 문자열 개수를 저장합니다. 길이 1인 문자열 "a", "b", …, "z"는 각각 하나씩 존재하므로 모든 arr[1][j]의 값은 1입니다.
나머지 arr[2 ~ num+1][0 ~ 25]에 대해서는 j=0('a'로 시작)일 때 arr[i][j] = arr[i-1][j+1]로 설정하고, 그 외의 경우에는 arr[i][j] = arr[i-1][j-1] + arr[i-1][j+1]로 설정합니다. 최종 결과는 num번째 행의 모든 값의 합입니다.
알고리즘 단계
- 정수 num을 입력받습니다.
- 함수 difference_strings(int num)은 num을 받아 인접 문자의 차이가 1인 문자열의 개수를 반환합니다.
- 초기 count 값을 0으로 설정합니다.
- 배열 arr[num + 1][27]을 모두 0으로 초기화합니다.
- arr[1][0 ~ 25]를 모두 1로 초기화합니다.
- 2중 for 루프를 사용하여 2행부터 마지막 행까지, 열 0부터 25까지 26개 알파벳 전체를 순회합니다.
- j=0일 때 시작 문자가 'a'이므로 arr[i][j] = arr[i - 1][j + 1]로 설정합니다.
- 그 외의 경우에는 arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1])로 설정합니다.
- 루프가 끝나면 마지막 행을 순회하며 arr[num][0 ~ 25]의 값을 count에 더합니다.
- count를 결과로 반환합니다.
이 알고리즘의 시간 복잡도는 O(num × 26), 공간 복잡도 역시 O(num × 27)로 매우 효율적입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int difference_strings(int num){
long int count = 0;
long int arr[num + 1][27];
memset(arr, 0, sizeof(arr));
for (int i = 0; i <= 25; i++){
arr[1][i] = 1;
}
for (int i = 2; i <= num; i++){
for (int j = 0; j <= 25; j++){
if (j == 0){
arr[i][j] = arr[i - 1][j + 1];
}
else{
arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1]);
}
}
}
for (int i = 0; i <= 25; i++){
count = (count + arr[num][i]);
}
return count;
}
int main(){
int num = 2;
cout<<"Count of strings where adjacent characters are of difference one are: "<<difference_strings(num);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다 −
Count of strings where adjacent characters are of difference one are: 50