문자열 str이 주어졌을 때, 이 문자열에서 마지막으로 반복되지 않는(non-repeating) 문자를 찾는 문제입니다. 예를 들어 입력 문자열이 "programming"이라면, 뒤에서부터 살펴볼 때 가장 먼저 발견되는 중복 없는 문자는 'n'입니다. 만약 조건을 만족하는 문자가 하나도 없다면 -1을 반환해야 합니다.
해결 접근 방법
이 문제는 빈도(frequency) 배열 하나만 있으면 간단하게 해결할 수 있습니다.
먼저 길이 256의 정수 배열을 선언하여 문자열에 등장하는 각 문자의 출현 횟수를 저장합니다. 아스키(ASCII) 코드 기준으로 가능한 모든 문자를 커버하기 위해 크기를 256으로 설정한 것입니다.
빈도 계산이 완료되면, 문자열을 마지막 문자부터 첫 번째 문자까지 거꾸로 순회하면서 현재 문자의 저장된 빈도 값이 1인지 확인합니다. 빈도가 1이라면 그 문자가 곧 마지막 반복되지 않는 문자이므로 즉시 반환하고, 1이 아니라면 이전 문자로 이동해 같은 과정을 반복합니다.
알고리즘 단계
- 길이 256의 빈도 배열을 생성하고 0으로 초기화합니다.
- 문자열을 앞에서부터 순회하며 각 문자의 빈도를 증가시킵니다.
- 문자열을 뒤에서부터 다시 순회하며 빈도가 1인 문자를 찾습니다.
- 찾으면 해당 문자를 반환하고, 끝까지 찾지 못하면 "-1"을 반환합니다.
예제 코드
#include <iostream>
using namespace std;
const int MAX = 256;
static string searchNonrepeatChar(string str) {
int freq[MAX] = {0};
int n = str.length();
for (int i = 0; i < n; i++)
freq[str.at(i)]++;
for (int i = n - 1; i >= 0; i--) {
char ch = str.at(i);
if (freq[ch] == 1) {
string res;
res += ch;
return res;
}
}
return "-1";
}
int main() {
string str = "programming";
cout << "Last non-repeating character: " << searchNonrepeatChar(str);
}실행 결과
Last non-repeating character: n
복잡도 분석
- 시간 복잡도: O(n) — 문자열을 두 번 순회하므로 문자열 길이에 비례합니다.
- 공간 복잡도: O(1) — 고정 크기(256)의 빈도 배열만 사용하므로 상수 공간입니다.
이처럼 빈도 배열과 역방향 탐색을 조합하면 별도의 자료구조 없이도 효율적으로 마지막 반복되지 않는 문자를 찾을 수 있습니다.