C++로 화학식의 원자 개수 계산하기

문제 개요

화학식(chemical formula)이 문자열로 주어졌을 때, 식에 포함된 각 원소의 개수를 구하는 프로그램을 작성해 보겠습니다.

원소 기호는 항상 대문자로 시작하며, 그 뒤에 0개 이상의 소문자가 붙어 하나의 원소 이름을 이룹니다. 또한 해당 원소의 개수가 1보다 크다면 그 뒤에 1개 이상의 숫자가 따라올 수 있습니다. 반면 개수가 1인 경우에는 숫자를 생략합니다. 예를 들어 H2O나 H2O2는 모두 올바른 형태지만, H1O2처럼 개수 1을 명시하는 것은 허용되지 않습니다.

예를 들어 입력이 Na2(CO)3이라면 출력은 C3Na2O3이 되어야 합니다. 이 결과는 탄소(C) 3개, 나트륨(Na) 2개, 산소(O) 3개가 포함되어 있음을 의미하며, 원소 이름은 사전순으로 정렬되어 출력됩니다.

접근 방법

괄호가 포함된 중첩 구조를 처리하기 위해 스택(stack)과 맵(map) 두 가지 자료구조를 활용합니다. 맵은 원소 이름을 키로, 개수를 값으로 저장하며, 스택은 여는 괄호를 만날 때마다 현재까지의 누적 상태를 임시 저장하는 역할을 담당합니다.

1. 결과 문자열 생성 함수 — makeRet()

맵 m을 매개변수로 받습니다.
ret := 빈 문자열로 초기화합니다.
m의 각 키-값 쌍(it)에 대해 다음을 수행합니다.
- ret에 원소 이름(키)을 추가합니다.
- 개수(값)가 1보다 크면 개수를 문자열로 변환하여 ret에 이어 붙입니다.
완성된 ret을 반환합니다.

2. 원자 개수 계산 함수 — countOfAtoms()

입력 문자열 s를 받아 다음 과정을 수행합니다.

맵 m과 스택 st를 선언하고, 인덱스 i = 0, 문자열 길이 n = s.size()로 초기화합니다.
i < n인 동안 아래를 반복합니다.
- c := s[i]를 읽고 i를 1 증가시킵니다.
- c가 '('인 경우: 현재 맵 m을 스택 st에 push하고, m을 새로운 빈 맵으로 초기화합니다. 이렇게 하면 괄호 안쪽의 원소들을 별도로 집계할 수 있습니다.
- c가 ')'인 경우:
  - val := 0으로 초기화한 뒤, 연속된 숫자를 모두 읽어 괄호 뒤의 배율을 계산합니다.
  - temp := 스택의 최상단(top) 요소를 가져오고 pop합니다.
  - 현재 맵 m의 각 원소 개수에 val을 곱한 뒤 temp에 누적하고, m := temp로 갱신합니다.
- 그 외의 경우(원소 기호):
  - name := c부터 시작하여, 연속된 소문자를 모두 읽어 완전한 원소 이름을 만듭니다.
  - 연속된 숫자를 읽어 개수 val을 계산합니다.
  - val이 0이면 1로 설정합니다(개수가 생략된 경우의 기본값).
  - m[name]에 val을 더합니다.
반복이 끝나면 makeRet(m)의 결과를 반환합니다.

구현 예제 (C++)

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string makeRet(map<string, int> m){
        string ret = "";
        for (auto& it : m) {
            ret += it.first;
            if (it.second > 1) {
                ret += to_string(it.second);
            }
        }
        return ret;
    }
    string countOfAtoms(string s){
        map<string, int> m;
        stack<map<string, int> > st;
        int i = 0;
        int n = s.size();
        while (i < n) {
            char c = s[i];
            i++;
            if (c == '(') {
                st.push(m);
                m = map<string, int>();
            }
            else if (c == ')') {
                int val = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    val = val * 10 + (s[i] - '0');
                    i++;
                }
                map<string, int> temp = st.top();
                st.pop();
                for (auto& it : m) {
                    it.second *= val;
                    temp[it.first] += it.second;
                }
                m = temp;
            }  
            else {
                string name = "";
                int val = 0;
                name += c;
                while (i < n && s[i] >= 'a' && s[i] <= 'z') {
                    name += s[i];
                    i++;
                }
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    val = val * 10 + (s[i] - '0');
                    i++;
                }
                val = val == 0 ? 1 : val;
                m[name] += val;
            }
        }
        return makeRet(m);
    }
};
main(){
    Solution ob;
    cout << (ob.countOfAtoms("Na2(CO)3"));
}

실행 결과

입력:

Na2(CO)3

출력:

C3Na2O3

정리 및 시간 복잡도

std::map은 내부적으로 균형 이진 탐색 트리를 사용하므로 키가 자동으로 사전순으로 정렬됩니다. 덕분에 결과 문자열을 만들 때 별도의 정렬 과정 없이도 원소 이름이 알파벳 순서대로 출력됩니다.

이 알고리즘의 시간 복잡도는 문자열 길이를 N이라 할 때 O(N² log N) 수준으로 평가할 수 있으며, 괄호가 깊게 중첩되지 않는 일반적인 입력에서는 충분히 효율적으로 동작합니다. 스택을 활용한 이 방식은 괄호가 몇 겹으로 중첩되어 있더라도 안정적으로 원자 개수를 집계할 수 있다는 것이 가장 큰 장점입니다.