BOJ 3059 - 등장하지 않는 문자의 합

문제

대문자로 이루어진 문자열이 주어질 때, A~Z 중 등장하지 않는 문자들의 ASCII 값 합을 구하라.

입력

첫째 줄에 테스트 케이스 수 T, 이후 T줄에 문자열이 주어진다.

출력

각 테스트 케이스마다 등장하지 않는 문자의 ASCII 합을 출력한다.

예제

입력	출력
`2` `ABCDEFGHIJKLMNOPQRSTUVW` `A`	`267` `1950`

풀이

등장 문자를 체크 배열로 표시하고, 미등장 문자의 ASCII 합을 구한다.

문자열의 각 문자를 체크 배열에 표시한다
A(65)부터 Z(90)까지 순회하며 체크되지 않은 문자의 ASCII 값을 합산한다
합산 결과를 출력한다

핵심 아이디어: A~Z의 ASCII 총합(2015)에서 등장한 문자의 합을 빼는 것과 동일하며, 체크 배열로 O(N + 26)에 해결한다.

코드

#include <bits/stdc++.h>
using namespace std;
int T, ch[100], ans;
string s;
void solve()
{
  ans = 0;
  memset(ch, 0, sizeof(ch));
  for (int i : s)
    ch[i] = 1;
  for (int i = 65; i <= 90; i++)
    if (!ch[i])
      ans += i;
}
int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> T;
  while (T--)
  {
    cin >> s;
    solve();
    cout << ans << "\n";
  }
  return 0;
}

복잡도

시간: O(T * (N + 26)) (N: 문자열 길이)
공간: O(1)

문제