백준 3059번 [등장하지 않는 문자의 합](C++) -yes6686- 티스토리

백준 문제 풀이: 3059 [등장하지 않는 문자들의 합]

---

문제 링크: https://www.acmicpc.net/problem/3059

문제 설명:

대문자 알파벳으로 구성된 문자열이 주어질 때, 알파벳 A부터 Z까지 중 문자열에 등장하지 않은 알파벳의 ASCII 값의 합을 구하는 문제입니다. 여러 테스트 케이스가 주어질 수 있습니다.

---

문제 해결 코드

#include <iostream>
#include <string>
#include <cstring> // memset 함수 사용
using namespace std;

int alpha[26]; // 알파벳 등장 여부 저장 배열

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n; // 테스트 케이스 수 입력

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s; // 입력 문자열

        // 등장한 알파벳 체크
        for (int j = 0; j < s.size(); j++) {
            alpha[s[j] - 'A'] = 1;
        }

        // 등장하지 않은 알파벳의 ASCII 값 합산
        int sum = 0;
        for (int j = 0; j < 26; j++) {
            if (alpha[j] == 0) {
                sum += 65 + j; // 'A'의 ASCII 값은 65
            }
        }

        // 결과 출력
        cout << sum << '\n';

        // 배열 초기화
        memset(alpha, 0, sizeof(alpha));
    }

    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • 주어진 문자열을 순회하며 등장한 알파벳을 기록합니다.
  • A부터 Z까지의 알파벳 중 등장하지 않은 알파벳의 ASCII 값을 합산합니다.
• 구현 세부사항:
  • alpha 배열은 알파벳이 등장했는지를 나타내며, 초기값은 0입니다.
  • 문자열의 각 문자를 순회하며 alpha[s[j] - 'A']를 1로 설정하여 등장 여부를 기록합니다.
  • A부터 Z까지의 ASCII 값은 65부터 90이며, 등장하지 않은 알파벳의 값만 합산합니다.
  • 매 테스트 케이스가 끝날 때 memset를 사용해 alpha 배열을 초기화합니다.
• 시간 복잡도 분석:
  • 각 문자열에 대해 O(26 + |s|)의 시간이 필요합니다. 여기서 |s|는 문자열의 길이입니다.
  • 전체 시간 복잡도는 O(n ⋅ (26 + |s|))이며, 문자열 길이가 작기 때문에 효율적입니다.

---

결과

각 테스트 케이스에 대해 문자열에 등장하지 않는 알파벳의 ASCII 값의 합을 정확히 계산하여 출력합니다.

해당 문제에 대한 다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!