문제 요약:
Input:
formula = "K4(ON(SO3)2)2"
Output:
"K4N2O14S4"
원소기호와 기호 바로뒤에 원소의 개수가 따라온다
닫히는 괄호 바로 다음에 숫자가 따라온다면 괄호 안의 전체 원소를 해당 수 만큼 곱한다
원소의 개수가 1개인 경우에는 표기하지 않는다
주어진 원소 기호 공식의 괄호를 모두 벗겨낸 결과물을 반환하라
출력시 원소기호는 정렬되며 첫글자가 같은 경우엔 다음 글자를 비교한다
들어오는 공식들은 모두 32bit 정수형을 넘지 않도록 설계되어 있다
풀이 과정:
처음에는 재귀, 스택이 떠올랐지만 재귀는 피하고 싶어서 보류했다
우선은 숫자만 따로 두어야할 필요가 있다고 생각이 들었다
그 이유로는 숫자만 따로 모아서 괄호를 기준으로 연산을 진행하게되면 연산이 편해질수 있으며 연산 후에 남은 숫자들은 분리한 원소기호들의 개수와 인덱스번호까지 같으므로 기호와 개수를 쌍으로 맵으로 정렬을 하고 문자열로 변환 시키면 되겠다는 생각이 들었다
풀이 결과:
실패한 풀이법
런타임속도는 100%가 나왔지만 이는 그냥 주어진 입력값들이 그리 길지 않아서일 뿐, 내가잘했다는 생각은 없다
메모리사용은 최악이었다 이리저리 변환을 하면서 다른 타입들의 벡터와 맵과 같은 여러 자료구조들을 사용을 했으니 당연한 결과였다
문제는 난이도에 맞게 구현이 힘들었지만 이론자체는 어려운것이 아니라 밀어붙이면 충분히 할 수 있었다
솔직히 도중에 내 풀이법이 그리 좋지 않다는 생각은 들었으나 완성은 해야했고 재귀 외에는 다른 방식은 떠오르지 않아 그대로 진행했다
내 풀이법의 문제는 공간을 너무 낭비한 것이라 볼 수 있는데 공간을 낭비함과 동시에 그 공간을 만들고 채우기 위한 시간도 낭비하게 되었다
배운점 및 코드:
- 재귀라고 피하지말고 필요하다면 재귀를 쓰는게 맞다
- map은 기본적으로 정렬되어 들어간다
- iterator에 읽기 전용으로 const_iterator가 존재하는데 이를 이용하기 위해서는 cbegin(), cend()를 사용해야한다
- 문제를 풀때 미리 생각을 해야된다 생각은 물론이고 도중에 잘못된다면 언제든 빠져나올수 있어야한다
#include <stack>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <cctype>
using namespace std;
class Solution {
public:
string countOfAtoms(string formula) {
vector<string> atomNames;
vector<string> atomNums;
vector<int> nums;
string result;
setAtoms(formula, atomNames, atomNums);
nums = calcAtomNums(atomNums);
result = getResult(atomNames, nums);
return result;
}
string getResult(vector<string> atomNames, vector<int> nums) {
int size = atomNames.size();
map<string, int> atoms;
string result = "";
//map에서 동일한 key가 있다면 value를 더해주고 없다면 value 추가
for (int index = 0; index < size; ++index) {
if (atoms.find(atomNames[index]) != atoms.end())
atoms[atomNames[index]] += nums[index];
else
atoms[atomNames[index]] = nums[index];
}
//map을 순회하며 key, value값을 번갈아가며 string에 추가
for (std::map<std::string, int>::const_iterator it = atoms.cbegin(); it != atoms.cend(); ++it) {
result += it->first;
//value가 1인경우 추가하지 않음
if (it->second != 1)
result += to_string(it->second);
}
return result;
}
vector<int> calcAtomNums(vector<string> atomNums) {
int size = atomNums.size();
int moved = 0;
vector<int> nums(size);
//string to int
//괄호는 음수로 구별
for (int index = 0; index < size; ++index) {
if (atomNums[index][0] == '(')
nums[index] = -2;
else if (atomNums[index][0] == ')')
nums[index] = -1;
else
nums[index] = stoi(atomNums[index]);
}
//숫자들만 가지고 연산 및 괄호와 곱에 사용된 숫자는 전부 0으로 처리
for (int index = 1; index < size; ++index) {
moved = 1;
if (nums[index - 1] == -1)
{
nums[index - 1] = 0;
while (nums[index - 1 - moved] != -2)
nums[index - 1 - moved++] *= nums[index];
nums[index - 1 - moved] = 0;
nums[index] = 0;
}
}
//remove zero
nums.erase(std::remove(nums.begin(), nums.end(), 0), nums.end());
return nums;
}
//불필요하게 문자열 벡터를 만들지 않고 정수형 벡터를 만들어서 바로 사용했다면 좋았을 것
//밑의 atomNum을 채우는 부분에서 정수형으로 채웠다면 두번 변환하는 수고를 덜 수 있었을 것
void setAtoms(
string formula,
vector<string> &atomNames,
vector<string> &atomNums
) {
int len = formula.length(), index = 0;
string atomName = "", atomNum = "";
while (index < len)
{
if (formula[index] == '(' || formula[index] == ')')
{
atomNum = formula[index];
atomNums.push_back(atomNum);
index++;
if (index && formula[index - 1] == ')' && !isdigit(formula[index]))
atomNums.push_back("1");
}
else
{
atomName = getAtomName(formula, index);
if (atomName[0])
atomNames.push_back(atomName);
atomNum = getAtomNum(formula, index);
if (atomNum[0])
atomNums.push_back(atomNum);
}
}
}
string getAtomName(string formula, int &index) {
string atomName = "";
if (isupper(formula[index]))
{
atomName += formula[index++];
while (formula[index] && islower(formula[index]))
atomName += formula[index++];
}
return atomName;
}
//애초에 이곳에서 string to int를 하는 편이 더 좋았을 것 같다
string getAtomNum(string formula, int &index) {
string atomNum = "";
if (isdigit(formula[index]))
{
while (formula[index] && isdigit(formula[index]))
atomNum += formula[index++];
}
else
atomNum = "1";
return atomNum;
}
};
답들을 보니 해결방법들이 굉장히 많았고 재귀가 꽤 많은 것을 알 수 있었다
공부해야겠다
