문자열들이 담긴 리스트가 있다고 가정해 보겠습니다. 이 리스트에는 중복된 문자열이 일부 포함되어 있으며, 우리는 어떤 문자열이 두 번 이상 등장했는지 찾아 화면에 출력해야 합니다.
예를 들어 문자열 리스트가 ["Hello", "Kite", "Hello", "C++", "Tom", "C++"]와 같다면, 결과로 "Hello"와 "C++"이 출력되어야 합니다.
접근 방법: 해싱(Hashing) 기법 활용
이 문제는 해싱 기법을 사용하면 효율적으로 해결할 수 있습니다. 알고리즘의 흐름은 다음과 같습니다.
- 빈 해시 테이블 역할을 하는
std::unordered_set을 생성합니다. - 벡터의 각 문자열을 하나씩 순회하며, 해당 문자열이 이미 집합에 존재하는지 확인합니다.
- 이미 존재한다면 중복 문자열이므로 화면에 출력하고, 존재하지 않는다면 집합에 새로 삽입합니다.
C++ STL의 std::unordered_set은 내부적으로 해시 테이블로 구현되어 있어 원소의 삽입과 탐색을 평균 O(1) 시간에 처리할 수 있습니다. 따라서 전체 알고리즘의 시간 복잡도는 O(n)으로 매우 효율적입니다.
예제 코드
#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;
void displayDuplicateStrings(vector<string> strings) {
unordered_set<string> s;
bool hasDuplicate = false;
for (int i = 0; i < strings.size(); i++) {
if (s.find(strings[i]) != s.end()) {
cout << strings[i] << endl;
hasDuplicate = true;
}
else
s.insert(strings[i]);
}
if (!hasDuplicate)
cout << "No Duplicate string has found" << endl;
}
int main() {
vector<string> strings{"Hello", "Kite", "Hello", "C++", "Tom", "C++"};
displayDuplicateStrings(strings);
}출력 결과
Hello C++
코드 설명
displayDuplicateStrings 함수는 문자열 벡터를 입력받아 중복된 문자열을 찾아 출력합니다. s.find()는 집합에서 해당 문자열을 검색하며, 반환값이 s.end()와 같지 않으면 문자열이 이미 존재한다는 의미입니다. 이 경우 해당 문자열을 출력하고 hasDuplicate 플래그를 true로 설정합니다.
만약 모든 문자열을 순회한 후에도 중복이 발견되지 않았다면, "No Duplicate string has found"라는 메시지를 출력하여 중복이 없음을 알려줍니다.
이 방식은 각 문자열을 한 번씩만 검사하므로, 정렬 기반 접근(O(n log n))보다 빠르며 대용량 데이터에서도 안정적인 성능을 보여줍니다.