문제
문장이 주어질 때, 대소문자 구분 없이 사용된 서로 다른 알파벳의 개수를 출력하라.
입력
여러 줄에 걸쳐 문장이 주어진다. "#"이 입력되면 종료한다.
출력
각 문장에 대해 서로 다른 알파벳 개수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
The quick brown fox # | 15 |
풀이
문자열을 소문자로 변환하고 알파벳 등장 배열로 중복 없이 센다.
transform으로 문자열 전체를 소문자로 변환한다- 크기 26의 빈도 배열을 0으로 초기화한다
- 각 문자에서
'a'를 빼 알파벳 인덱스를 구하고, 유효하면 카운트를 증가시킨다 - 빈도가 1 이상인 알파벳의 개수를 세어 출력한다
핵심 아이디어: 크기 26의 고정 배열로 알파벳 등장 여부만 추적하면 O(L)에 해결된다.
코드
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
using namespace std;
int main()
{
string sentence;
while (1)
{
getline(cin, sentence);
if (sentence == "#")
{
break;
}
int alpha[26]{0};
transform(sentence.begin(), sentence.end(), sentence.begin(), ::tolower);
int len = sentence.length();
for (int i = 0; i < len; i++)
{
int number = sentence[i] - 'a';
if (number >= 0 && number <= 26)
{
alpha[sentence[i] - 'a']++;
}
}
int answer = 0;
for (auto &ele : alpha)
{
if (ele > 0)
{
answer++;
}
}
cout << answer << "\n";
}
return 0;
}복잡도
- 시간: O(T * L) (T: 문장 수, L: 문장 길이)
- 공간: O(1)