C++에서 문자열의 첫 번째 반복 문자 찾기
- C++의 문자열에서 첫 번째 반복 문자 찾기
- 해싱 기술을 사용하여 C++에서 문자열의 첫 번째 반복 문자 찾기
- Brute-Force 방법을 사용하여 C++에서 문자열의 첫 번째 반복 문자 찾기
이 자습서에서는 C++에서 문자열의 첫 번째 반복 문자를 찾는 방법을 배웁니다. 이 목적을 달성하기 위한 세 가지 접근 방식인 해싱 기술, 무차별 대입 방식 및 알고리즘 작성을 배우게 됩니다.
C++의 문자열에서 첫 번째 반복 문자 찾기
알고리즘 작성을 시도하는 방법에는 두 가지가 있습니다. 첫 번째는 문자열을 왼쪽에서 오른쪽으로 순회하는 것이고 두 번째 방법은 문자열을 오른쪽에서 왼쪽으로 순회하면서 방문한 문자를 추적하는 것입니다. 두 번째 방법은 더 적은 수의 비교를 수행하여 더 효율적이기 때문에 다른 방법보다 성능이 우수합니다.
정렬 알고리즘은 O(n Log n) 시간에 문자열에서 첫 번째 반복 문자를 찾는 데 도움이 될 수 있습니다. 그러나 ASCII 코드를 사용하여 문자열을 반복하고 문자를 해시하고 해시 배열에서 루프를 실행하고 반복되는 문자의 최소 위치를 찾을 수 있습니다.
코드 예:
#include <iostream>
using namespace std;
#define numberChar 256
// left most string
int farLeftStr(string& primeStr) {
// represents the first index
int IndexNum[numberChar];
for (int i = 0; i < numberChar; i++) IndexNum[i] = -1;
// represents the resultIndexNum
int resultStr = INT_MAX;
for (int i = 0; i < primeStr.length(); i++) {
if (IndexNum[primeStr[i]] == -1)
IndexNum[primeStr[i]] = i;
else
resultStr = min(resultStr, IndexNum[primeStr[i]]);
}
return (resultStr == INT_MAX) ? -1 : resultStr;
}
int main() {
string primeStr = "HouseOfTheDragons";
int left = farLeftStr(primeStr);
if (left == -1)
cout << "All characters are distinct or string is empty ";
else
cout << "The first repeating character is: " << primeStr[left];
return 0;
}
출력:
The first repeating character is: o
문자열을 왼쪽에서 오른쪽으로 순회하는 것은 모든 문자의 첫 번째 인덱스를 -1로 초기화하는 것과 관련하여 수행할 수 있습니다. 반복되는 문자의 첫 번째 또는 맨 왼쪽 인덱스(만나는 경우)를 현재 결과와 비교할 수 있습니다.
또한 O(N²) 복잡도를 사용하여 각 문자를 연구하고 나머지 문자열에서 동일한 항목을 검색하여 이 문제를 해결할 수 있습니다.
해싱 기술을 사용하여 C++에서 문자열의 첫 번째 반복 문자 찾기
Count 배열은 첫 번째 반복 문자를 찾고 문자열에서 반복되는 문자 수를 유지할 수 있습니다.
해싱 기술은 네 가지 기본 단계로 구성됩니다.
- 하나의 해시 테이블 생성.
- 문자 스캔.
- 존재하지 않는 경우 해시 테이블에 문자를 삽입합니다.
- 그렇지 않으면 해당 문자를 중복으로 반환합니다.
코드 예:
#include <iostream>
// hashing function object type
#include <unordered_set>
using namespace std;
char getRepeatingChar(string &str) {
unordered_set<char> hashObj;
for (int i = 0; i < str.length(); i++) {
char repChar = str[i];
if (hashObj.find(repChar) != hashObj.end())
return repChar;
else
hashObj.insert(repChar);
}
return '\0';
}
int main() {
string expStr = "GameOfThrones";
cout << "The first repeating character is: " << getRepeatingChar(expStr);
}
출력:
The first repeating character is: e
이 문제의 또 다른 유명한 변형은 Count가 1과 같은 경우 결과를 인쇄하여 문자열에서 첫 번째 고유하거나 반복되지 않는 문자를 인쇄하는 것입니다. 원래 기술의 확장된 변형으로 문자열의 모든 반복 문자를 인쇄할 수 있지만 기본 해싱 방법만큼 간단하지는 않습니다.
사용자가 Count 배열을 생성해야 하므로 이 방법의 시간 복잡도는 O(n)이 됩니다. 최악의 경우 반복이 없고 추가 공간이 없으면 시간 복잡도는 O(1)이 됩니다.
Brute-Force 방법을 사용하여 C++에서 문자열의 첫 번째 반복 문자 찾기
프로그래머가 문자열의 각 문자를 확인하여 반복되는 문자를 찾고 해당 결과를 출력할 수 있는 간단한 방법입니다. 끝 문자열에 도달하거나 마지막 문자가 스캔되면 반복 문자가 발견되지 않으며 기본적으로 반복 문자가 없습니다.
최악의 시나리오에서 반복이 없는 경우 시간 복잡도는 O(n2)이고 최상의 시나리오는 O(1)로 두 번째 위치에 반복 문자가 있음을 나타냅니다. . 일정한 양의 메모리를 사용하는 카운트 배열이 필요하므로 무차별 대입 방법 이상이며 필요한 총 추가 공간은 O(1), 즉 상수입니다.
코드 예:
#include <iostream>
using namespace std;
int main() {
string expStr = "Hello World!";
string primeExp = "";
// check the boundary of the `expStr` string
if (expStr == primeExp) {
cout << "The string is empty!";
}
for (int a = 0; expStr[a] != '\0'; a++) {
for (int b = a + 1; expStr[b] != '\0'; b++) {
if (expStr[a] == expStr[b]) {
cout << "The first repeating character is: " << expStr[a];
}
break;
}
}
}
출력:
The first repeating character is: l
Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.
GitHub