[LeetCode] 726. Number of Atoms

https://leetcode.com/problems/number-of-atoms/description/

leetcode - Number of Atoms

문제 유형 : 스택, 재귀, 문자열 처리

문제 난이도 : Hard

 

문제

Given a string formula representing a chemical formula, return the count of each atom.

The atomic element always starts with an uppercase character, then zero or more lowercase letters, representing the name.

One or more digits representing that element's count may follow if the count is greater than 1. If the count is 1, no digits will follow.

• For example, "H2O" and "H2O2" are possible, but "H1O2" is impossible.

Two formulas are concatenated together to produce another formula.

• For example, "H2O2He3Mg4" is also a formula.

A formula placed in parentheses, and a count (optionally added) is also a formula.

• For example, "(H2O2)" and "(H2O2)3" are formulas.

Return the count of all elements as a string in the following form: the first name (in sorted order), followed by its count (if that count is more than 1), followed by the second name (in sorted order), followed by its count (if that count is more than 1), and so on.

The test cases are generated so that all the values in the output fit in a 32-bit integer.

 

문자열 화학식이 주어진다. 

각 원소의 개수를 정리하여 반환하여야 합니다.

원소의 개수가 1이면 표시하지 않아야 합니다.

두 개의 화학식은 접합이 가능합니다.

화학식을 괄호로 묶고 뒤에 곱할 숫자를 놓는 것도 화학식입니다.

 

문자열을 파싱하시오.

 

풀이

문자열을 파싱할 때, 3가지 경우가 있다.

• 닫는 괄호이거나, 문자열의 끝
• 여는 괄호
• 원소(upperCase letter로 시작해서 0개이상의 lowerCase letter, x자리의 10진수 문자열이 접합된 꼴)

우리는 문자열 파싱을 재귀를 통해서 할 것이다.

여는 괄호를 만나면, 재귀호출을 하면 되겠다.

닫는 괄호를 만나면, 리턴하면 되겠다.

root(최초의 함수 호출)에서는 문자열의 끝을 만나면 리턴하면 되겠다.

리턴하는 형태는 해시맵<string : int>의 꼴이면 되겠다.

괄호가 아닌 일반 원소의 경우에는, 슬라이딩 윈도우 기법을 이용해서 원소 문자열과 숫자를 읽고 해시맵에 저장시키면 되겠다.

 

최종적으로 반환된 해시맵을 배열에 담아서 원소의 화학식대로 정렬시키고, 정답으로 제출할 문자열을 빈 문자열로 선언한 뒤, 각 원소별로 원소의 화학식과 개수를 접합시켜서 반환하면 된다.

 

코드

C++

class Solution {
public:
    string parseAtomName(const string& formula, int& i) {
        string name;
        name += formula[i++];
        while (i < formula.size() && islower(formula[i])) {
            name += formula[i++];
        }
        return name;
    }

    int parseMultiplier(const string& formula, int& i) {
        int multiplier = 0;
        while (i < formula.size() && isdigit(formula[i])) {
            multiplier = multiplier * 10 + (formula[i++] - '0');
        }
        return multiplier == 0 ? 1 : multiplier;
    }

    unordered_map<string, int> parseFormula(const string& formula, int& i) {
        unordered_map<string, int> atomCount;
        int n = formula.size();
        while (i < n && formula[i] != ')') {
            if (formula[i] == '(') {
                i++;
                unordered_map<string, int> innerCount = parseFormula(formula, i);
                i++;
                int multiplier = parseMultiplier(formula, i);
                for (const auto& pair : innerCount) {
                    atomCount[pair.first] += pair.second * multiplier;
                }
            } else {
                string name = parseAtomName(formula, i);
                int count = parseMultiplier(formula, i);
                atomCount[name] += count;
            }
        }
        return atomCount;
    }
    string countOfAtoms(string formula) {
        int i = 0;
        unordered_map<string, int> atomCount = parseFormula(formula, i);
        vector<pair<string, int>> sortedAtoms(atomCount.begin(), atomCount.end());
        sort(sortedAtoms.begin(), sortedAtoms.end());

        string result;
        for (const auto& atom : sortedAtoms) {
            result += atom.first;
            if (atom.second > 1) {
                result += to_string(atom.second);
            }
        }
        return result;
    }
};