Closed KodaHye closed 3 weeks ago
=> O(26 20 26) : 완전탐색 가능
tree의 0번째 인덱스(tIdx
), skill의 0번째 인덱스(sIdx)
부터 시작 => 스킬은 0번째부터 차례대로 찾을 수 있어야 함tree.charAt(tIdx) == skill.charAt(sIdx)
라면 스킬을 찾은 것이므로 둘 다 인덱스 증가 tIdx+1, sIdx+1
tIdx+1
만 증가O(n * p * m)
queue
에 넣음1 <= skill_trees <= 20
길이 , 2 <= skill_trees <= 26
O(20*26)
으로 단순 구현으로 가능한 크기1 <= skill_trees의 길이 <= 20
1 <= 선행 스킬 순서 길이 <= 26
이므로 별다른 알고리즘을 사용하지 않고 구현해도 시간이 충분할 것이라고 판단
HashMap<Character, Integer> hashMap
skill
에서 알파벳 별로 순서 저장idx = 0
부터 skill.length -1
까지 확인
for(int i = 0; i < skill_tree[i].length(); i++) {
if(hashMap.get(s.charAt(i) > idx)) // 불가능한 스킬트리
}
if (sk.contains(c)) sb.append(c);
if (skill.startsWith(sb.toString())) cnt++;
정규 표현식
으로 다른 문자들 제거
"CBD"
순이라면 → "[^CBD]"
로 정규 표현식을 만든 뒤 replaceAll(regex, "")
을 이용하여 문자 제거
"BACDE" → "BCD"
"CBADF" → "CBD"
"AECB" → "CB"
"BDA" → "BD"
startsWith
이나 indexOf
써서 확인!!