C++에서 영어 알파벳과 같은 거리에 있는 문자 쌍 개수 구하기

문제 소개

문자열이 하나 주어졌을 때, 문자열 내에서 두 문자가 떨어져 있는 위치(인덱스) 간격과 알파벳 순서상 두 문자 사이의 거리가 서로 같은 문자 쌍의 개수를 계산하는 것이 이번 문제의 목표입니다.

입력 − str = 'Tutorials Point'

출력 − 영어 알파벳과 같은 거리에 있는 문자 쌍의 개수: 5

설명 − 알파벳에서의 거리가 문자열 내 위치 거리와 일치하는 문자 쌍은 (u, t), (u, r), (t, r), (i, o), (s, n) 입니다. 따라서 총 5개의 쌍이 존재합니다.

입력 − str = 'Learning is the best habit'

출력 − 영어 알파벳과 같은 거리에 있는 문자 쌍의 개수: 12

설명 − 조건을 만족하는 문자 쌍은 (r, i), (r, h), (n, i), (n, b), (i, g), (n, t), (g, i), (i, b), (s, h), (h, t), (s, t), (a, b) 입니다. 따라서 총 12개의 쌍이 존재합니다.

프로그램에 적용된 접근 방식

• 문자열을 입력받아 함수로 전달합니다.

• 만들 수 있는 쌍의 총 개수를 저장할 임시 변수 count를 선언합니다.

• length() 함수를 사용해 문자열의 길이를 구합니다.

• i를 0부터 문자열 길이까지 반복하는 FOR 루프를 시작합니다.

• 바깥 루프 안에서 j를 i+1부터 문자열 길이까지 반복하는 중첩 FOR 루프를 시작합니다.

• 루프 내부에서 temp를 abs(str[i] - str[j]), 즉 두 문자의 알파벳 거리로 설정합니다.

• temp가 abs(i - j), 즉 두 문자의 인덱스 거리와 같은지 확인하고, 참이라면 count를 1 증가시킵니다.

• 모든 반복이 끝나면 count를 반환합니다.

• 결과를 출력합니다.

이 방법은 모든 가능한 문자 쌍을 비교하므로 시간 복잡도는 O(n²)입니다. 문자열 길이가 짧거나 중간 정도일 경우 충분히 효율적으로 동작합니다.

예제

#include <bits/stdc++.h>
using namespace std;
int pairs_distance(string str){
   int count = 0;
   int len = str.length();
   for (int i = 0; i < len; i++){
      for (int j = i + 1; j < len; j++){
         int temp = abs(str[i] - str[j]);
         if (temp == abs(i - j)){
            count++;
         }
      }
   }
   return count;
}
int main(){
   string str = "Tutorials Point";
   cout<<"Count of character pairs at same distance as in English alphabets are: "<<pairs_distance(str);
   return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −

Count of character pairs at same distance as in English alphabets are: 5