문제 - 링크
문제 풀이
�팰린드룸 확인
- i 인덱스부터 j 인덱스로 이루어진 문자열이 팰린드룸인지 확인하기
- 문자 단 하나는 팰린드룸임
- 양 끝이 동일하고 차이가 1이라면 팰린드룸 , ex) aa
- 차이가 2 이상이라면 양 끝을 없앤 (i+1~j-1)으로 이루어진 문자열이 팰린드룸인지 확인
isPalindrome = new boolean[N][N];
for(int i = 0 ; i<N;i++){
isPalindrome[i][i] = true;
}
for(int i = N-1;i>=0;i--){
for(int j = i+1;j<N;j++){
// i~j가 팰린드룸인지 확인
// i와 j가 같은 문자라면
if (s.charAt(i) ==s.charAt(j)){
// i와 j의 차이가 1이라면 팰린드룸 , ex) aa
if(j-i==1) {
isPalindrome[i][j] = true;
}else{
// i~j가 팰린드룸이라면 i+1~j-1도 팰린드룸인지 확인
isPalindrome[i][j] = isPalindrome[i+1][j-1];
}
}
}
}문자열 쪼개기
- 주어진 팰린드룸으로 이루어진 문자열로 쪼개야 함
// s~e까지의 문자열을 팰린드룸으로 나누는 함수
private void rec(int s, int e, String str, List<String> route){
if(s==e){
result.add(route);
return;
}
// 문자열을 다음과 같이 쪼갤 것임
// [s, s+1, .... i] , i+1, ... e-1
// [s, s+1, .... i]가 팰린드룸이라면 다음 재귀 호출
for(int i = s;i<e;i++){
// s~i가 팰린드룸이라면 다음 재귀 호출
if(isPalindrome[s][i]){
List<String> newRoute = new ArrayList<>(route);
String substring = str.substring(s, i+1);
newRoute.add(substring);
// 다음 제귀 호출
rec(i + 1, e, str, newRoute);
}
}
}코드
class Solution {
public int solution(String skill, String[] skill_trees) {
int answer = 0;
int[] skillOrder = new int[26];
// 스킬트리 순서를 저장
// ex) "CBD" => C:1, B:2, D:3
for (int i = 0; i < skill.length(); i++) {
int idx = skill.charAt(i) - 'A';
skillOrder[idx] = i + 1;
}
fail:
for (String skill_tree : skill_trees) {
int skillDepth = 1;
int skillLen = skill_tree.length();
for (int i = 0; i < skillLen; i++) {
int idx = skill_tree.charAt(i) - 'A';
// 선행조건에 없는 스킬은 무시
// 선행조건에 있는 스킬이 순서에 맞지 않으면 실패
if (skillOrder[idx] == skillDepth) {
skillDepth++;
} else if (skillOrder[idx] > skillDepth) {
continue fail;
}
}
// 주어진 스킬트리가 선행조건에 만족하면 성공
answer++;
}
return answer;
}
}시간, 공간 복잡도
- 시간 복잡도 : O(N^2)
- 공간 복잡도 : O (N^2)
실행 시간
