이 문제에서는 하나의 문자열이 주어지며, 우리의 과제는 해당 문자열에 한 번만 등장하는 고유 문자들을 문자열에 나타난 순서 그대로 출력하는 것입니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: tutorials Point 출력: uralsPn
이 문제를 해결하는 방법은 여러 가지가 있지만, 여기서는 가장 효율적인 방법을 다룹니다. 가장 단순한 방법은 중첩 반복문을 사용하는 것이지만, 시간 복잡도가 O(n²)으로 비효율적입니다.
알고리즘 접근 방식
효율적인 해결을 위해 크기가 256인 두 개의 배열을 사용합니다(8비트 문자를 저장하기 위함).
- count 배열: 각 문자의 등장 횟수를 저장합니다.
- index 배열: 각 문자가 처음 등장한 위치(인덱스)를 저장합니다.
먼저 count 배열의 모든 값을 0으로, index 배열의 모든 값을 n(문자열 길이)으로 초기화합니다. 그다음 문자열 str을 순회하면서 각 문자 x에 대해 다음을 수행합니다.
- count[x]를 1 증가시킵니다.
- count[x]가 1이면(첫 등장), index[x] = i로 설정합니다.
- count[x]가 2가 되면(중복 등장), index[x] = n으로 되돌려 제외 대상으로 만듭니다.
마지막으로 index 배열을 정렬한 뒤, 유효한 인덱스에 해당하는 문자들을 순서대로 출력하면 됩니다. 이 방법의 시간 복잡도는 O(n log n)입니다.
구현 예제
위 알고리즘을 구현한 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 256;
void printDistinctCharacters(string str) {
int n = str.length();
int count[MAX_CHAR];
int index[MAX_CHAR];
// 배열 초기화
for (int i = 0; i < MAX_CHAR; i++) {
count[i] = 0;
index[i] = n;
}
// 문자열 순회
for (int i = 0; i < n; i++) {
char x = str[i];
++count[x];
if (count[x] == 1 && x != ' ')
index[x] = i; // 첫 등장 위치 기록
if (count[x] == 2)
index[x] = n; // 중복 문자는 제외
}
sort(index, index + MAX_CHAR);
for (int i = 0; i < MAX_CHAR && index[i] != n; i++)
cout << str[index[i]] << " ";
}
int main() {
string str = "tutorialsPoint";
cout << "문자열 '" << str << "'의 고유 문자들은 :\n";
printDistinctCharacters(str);
return 0;
}실행 결과
문자열 'tutorialsPoint'의 고유 문자들은 − u r a l s P n
출력 결과에서 확인할 수 있듯이, t·o·i처럼 두 번 이상 등장한 문자는 제외되고, u·r·a·l·s·P·n처럼 정확히 한 번만 등장한 문자들이 원래 순서대로 출력됩니다. 공백 문자는 조건문(x != ' ')을 통해 자동으로 걸러집니다.