문자열 str[]이 입력으로 주어졌을 때, 우리의 목표는 str[]과 길이가 같으면서 각 위치의 문자가 원래 단어의 (i-1)번째, i번째 또는 (i+1)번째 문자로 대체될 수 있는 단어의 개수를 세는 것입니다.
단, 첫 번째 문자는 i번째 또는 (i+1)번째 위치의 문자로만 대체할 수 있고, 마지막 문자는 (i-1)번째 또는 i번째 위치의 문자로만 대체할 수 있습니다.
예제를 통해 자세히 이해해 보겠습니다.
입력 − str[] = "TPP"
출력 − i번째 문자가 주어진 단어의 (i-1)번째, i번째 또는 (i+1)번째 문자가 될 수 있는 단어의 개수: 4
설명
T를 T(i번째) 또는 첫 번째 P((i+1)번째)로 교체 → TPP, PPP 첫 번째 P를 T((i-1)번째), P(i번째) 또는 P((i+1)번째)로 교체 → TTP, TPP, TPP 두 번째 P를 P((i-1)번째) 또는 P(i번째)로 교체 → TPP, TPP 교체 조합 중 고유한 단어: TPP, PPP, TTP, PTP
입력 − str = "aaa"
출력 − i번째 문자가 주어진 단어의 (i-1)번째, i번째 또는 (i+1)번째 문자가 될 수 있는 단어의 개수: 1
설명
첫 번째 a를 a(i번째) 또는 두 번째 a((i+1)번째)로 교체 → aaa, aaa 두 번째 a를 a((i-1)번째), a(i번째) 또는 a((i+1)번째)로 교체 → aaa, aaa, aaa 세 번째 a를 a((i-1)번째) 또는 a(i번째)로 교체 → aaa, aaa 교체 조합 중 고유한 단어: aaa
프로그램에서 사용하는 접근 방식
모든 문자에 대해 세 가지 가능성이 존재한다는 점을 이용합니다. 현재 문자 i 기준으로 (i-1)번째, i번째, (i+1)번째 문자가 모두 다르다면 선택지는 3개입니다. 두 개가 같다면 선택지는 2개이고, 세 개 모두 같다면 선택지는 1개뿐입니다.
따라서 문자열을 순회하면서 각 위치에서 고유한 선택지의 개수를 확인하고, 그 값(3, 2 또는 1)을 결과에 곱해 나갑니다. 첫 번째 문자와 마지막 문자는 선택 가능한 위치가 두 곳뿐이므로, 고유성을 검사한 뒤 2 또는 1을 곱하는 방식으로 처리합니다.
문자열 str[]을 문자 배열로 받습니다.
함수 total(char str[], int length)는 문자열과 길이를 인자로 받아, i번째 문자가 주어진 단어의 (i-1)번째, i번째 또는 (i+1)번째 문자가 될 수 있는 단어의 개수를 반환합니다.
초기 카운트를 1로 설정합니다. 이는 str[] 자신도 유효한 단어이기 때문입니다.
문자열 길이가 1이라면 그대로 1을 반환합니다.
인덱스 0의 첫 번째 문자를 검사합니다. str[0] == str[1]이라면 카운트에 1을 곱하고,
두 문자가 서로 다르다면 카운트에 2를 곱합니다.
이후 for 루프를 통해 인덱스 i=1부터 i<length-1까지, 즉 두 번째 문자부터 마지막에서 두 번째 문자까지 순회합니다.
각 인덱스 i에서 str[i]가 str[i-1] 또는 str[i+1]과 같은지 확인합니다. 세 문자가 모두 같다면 카운트에 1을 곱합니다.
세 문자 중 임의의 두 개가 같다면 카운트에 2를 곱합니다.
세 문자가 모두 다르다면 카운트에 3을 곱합니다.
마지막 문자에 대해서는 str[length-1] == str[length-2] 여부를 확인하여, 같으면 1을, 다르면 2를 곱합니다.
최종적으로 카운트에는 만들 수 있는 고유한 단어의 개수가 저장됩니다.
카운트를 결과로 반환합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
int total(char str[], int length){
int count = 1;
if (length == 1){
return count;
}
if (str[0] == str[1]){
count = count * 1;
}
else{
count = count * 2;
}
for (int j=1; j<length-1; j++){
if (str[j] == str[j-1] && str[j] == str[j+1]){
count = count * 1;
}
else if (str[j] == str[j-1]){
count = count * 2;
}
else if(str[j] == str[j+1]){
count = count * 2;
}
else if(str[j-1] == str[j+1]){
count = count * 2;
}
else{
count = count * 3;
}
}
if (str[length - 1] == str[length - 2]){
count = count * 1;
}
else{
count = count * 2;
}
return count;
}
int main(){
char str[] = "TPP";
int length = strlen(str);
cout<<"Count of words whose i-th letter is either (i-1)-th, i-th, or (i+1)-th letter of given word are: "<<total(str, length) << endl;
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Count of words whose i-th letter is either (i-1)-th, i-th, or (i+1)-th letter of given word are: 4