문제
주어진 단어가 화학 원소 기호의 연결로 표현될 수 있는지 판별하라.
입력
테스트 케이스 수 T와 각 케이스마다 알파벳 소문자 단어가 주어진다.
출력
각 단어에 대해 원소 기호로 분할 가능하면 YES, 아니면 NO를 출력한다.
예제
| 입력 | 출력 |
|---|---|
2 sno oo | YES NO |
풀이
DP + 메모이제이션으로 문자열의 각 위치에서 1글자 또는 2글자 원소 기호와 매칭을 시도한다.
- 114개의 원소 기호를 해시 셋에 저장한다
- 인덱스 idx부터 시작하여, 1글자 부분 문자열이 원소 기호이면 idx+1부터 재귀 탐색한다
- 2글자 부분 문자열이 원소 기호이면 idx+2부터 재귀 탐색한다
- 메모이제이션으로 각 인덱스의 결과를 캐싱하여 중복 계산을 방지한다
핵심 아이디어: 각 위치에서 최대 2가지 선택지(1글자, 2글자)만 있으므로, 메모이제이션으로 O(N) 시간에 해결된다.
코드
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std;
unordered_set<string> element = {
"h", "he", "li", "be", "b", "c", "n", "o", "f", "ne",
"na", "mg", "al", "si", "p", "s", "cl", "ar", "k", "ca",
"sc", "ti", "v", "cr", "mn", "fe", "co", "ni", "cu", "zn",
"ga", "ge", "as", "se", "br", "kr", "rb", "sr", "y", "zr",
"nb", "mo", "tc", "ru", "rh", "pd", "ag", "cd", "in", "sn",
"sb", "te", "i", "xe", "cs", "ba", "la", "ce", "pr", "nd",
"pm", "sm", "eu", "gd", "tb", "dy", "ho", "er", "tm", "yb",
"lu", "hf", "ta", "w", "re", "os", "ir", "pt", "au", "hg",
"tl", "pb", "bi", "po", "at", "rn", "fr", "ra", "ac", "th",
"pa", "u", "np", "pu", "am", "cm", "bk", "cf", "es", "fm",
"md", "no", "lr", "rf", "db", "sg", "bh", "hs", "mt", "ds",
"rg", "cn", "fl", "lv"};
vector<int> memo;
bool oath(string &s, int idx)
{
if (idx == s.size())
return true;
if (memo[idx] != -1)
return memo[idx];
string one = s.substr(idx, 1);
if (element.find(one) != element.end())
if (oath(s, idx + 1))
return memo[idx] = 1;
if (idx + 1 < s.size())
{
string two = s.substr(idx, 2);
if (element.find(two) != element.end())
if (oath(s, idx + 2))
return memo[idx] = 1;
}
return memo[idx] = 0;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int T;
bool chk = true;
string s, temp;
cin >> T;
while (T--)
{
cin >> s;
memo.resize(s.size(), -1);
if (oath(s, 0))
cout << "YES\n";
else
cout << "NO\n";
memo.clear();
}
return 0;
}복잡도
- 시간: O(N) (각 인덱스 최대 1번 방문)
- 공간: O(N)