이 문제에서는 크기가 N인 문자열 배열 str[]이 주어집니다. 우리의 과제는 주어진 배열에서 그 역순(뒤집은 문자열)이 같은 배열 안에도 존재하는 첫 번째 문자열을 찾는 프로그램을 작성하는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: str[] = ["python", "program", "C#", "language", "#C"]
출력: C#
위 예시에서 "C#"을 뒤집으면 "#C"가 되고, 이 값이 동일한 배열에 존재하므로 정답은 "C#"입니다.
해결 방법 1: 완전 탐색(Brute Force)
가장 직관적인 방법은 문자열 배열의 각 요소를 순회하면서, 해당 문자열의 역순이 나머지 배열 요소 중에 존재하는지 확인하는 것입니다. 역순 문자열을 발견하면 즉시 해당 문자열을 반환하고, 배열 전체를 탐색했음에도 조건을 만족하는 문자열이 없다면 -1을 반환합니다.
구현 예제
아래 프로그램은 이 해결 방법의 동작을 보여줍니다.
#include<iostream>
#include<string.h>
using namespace std;
bool checkStringRev(string s1, string s2)
{
if (s1.length() != s2.length())
return false;
int len = s1.length();
for (int i = 0; i < len; i++)
if (s1[i] != s2[len - i - 1])
return false;
return true;
}
string checkRevStringArr(string strArr[], int n){
for (int i = 0; i < n - 1; i++)
for (int j = i + 1; j < n; j++)
if (checkStringRev(strArr[i], strArr[j]))
return strArr[i];
return "-1";
}
int main(){
string strArr[] = { "python", "program", "C#", "language", "#C" };
int n = sizeof(strArr)/sizeof(strArr[0]);
cout<<"배열에서 역순이 함께 존재하는 문자열은 " <<checkRevStringArr(strArr, n);
}
출력 결과
배열에서 역순이 함께 존재하는 문자열은 C#
이 방법은 두 개의 중첩 반복문을 사용하기 때문에 시간 복잡도가 O(N² × L)입니다. 여기서 N은 배열의 크기, L은 문자열의 평균 길이입니다.
해결 방법 2: 해시맵(HashMap) 활용
문제를 선형 시간, 즉 단 한 번의 순회로 해결할 수 있는 더 효율적인 방법은 해시맵을 사용하는 것입니다. 각 단어를 해시맵에 저장해 가면서, 현재 문자열의 역순이 이미 해시맵에 존재하는지 확인합니다. 존재한다면 그 역순 문자열이 곧 우리가 찾는 결과입니다. 배열 전체를 탐색했는데도 그러한 문자열이 없다면 -1을 반환합니다.
구현 예제
아래 프로그램은 이 해결 방법의 동작을 보여줍니다.
#include<bits/stdc++.h>
using namespace std;
string checkRevStringArr(string strArr[], int length){
map<string,bool> stringHashMap;
for(int i = 0; i < length; i++) {
string str = strArr[i];
reverse(str.begin(),str.end());
if (stringHashMap.find(str) != stringHashMap.end() and stringHashMap[str])
return str;
else
stringHashMap[strArr[i]] = true;
}
return "-1";
}
int main(){
string strArr[] = { "python", "program", "C#", "language", "#C" };
int n = sizeof(strArr)/sizeof(strArr[0]);
cout<<"배열에서 역순이 함께 존재하는 문자열은 "<<checkRevStringArr(strArr, n);
}
출력 결과
배열에서 역순이 함께 존재하는 문자열은 C#
해시맵 기반 접근 방식은 배열을 한 번만 순회하며 각 연산이 평균적으로 상수 시간에 수행되므로, 전체 시간 복잡도가 O(N × L)로 완전 탐색 방식보다 훨씬 효율적입니다. 따라서 입력 크기가 클 경우 해시맵 방식을 사용하는 것이 좋습니다.