🙇♂️ URL : https://leetcode.com/problems/longest-string-chain/
🤷♂️ Difficulty: Medium
💆♂️ Submissions
- RunTime: 105 ms, faster than 10.50% of Java online submissions
- Memory Usage: 39.4 MB, less than 26.85% of Java online submissions
class Solution {
ArrayList<Integer> countList = new ArrayList<>();
public int longestStrChain(String[] words) {
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});
boolean[] visited = new boolean[words.length];
for(int i = 0; i<words.length; i++) {
if(!visited[i]) {
dfs(words, i, 1, visited);
visited[i] = true;
}
}
return Collections.max(countList);
}
public void dfs(String[] words, int curr, int count, boolean[] visited) {
boolean check = false;
for(int i = curr+1; i<words.length; i++) {
if(!visited[i] && checkSimilar(words[curr], words[i])) {
dfs(words, i, count+1, visited);
visited[i] = true;
check = true;
}
}
if(check == false) {
countList.add(count);
return;
}
}
public boolean checkSimilar(String a, String b) {
if(b.length() - a.length() != 1) {
return false;
}
Queue<Character> aq = new LinkedList<>();
Queue<Character> bq = new LinkedList<>();
for(int i=0; i<a.length(); i++) {
aq.offer(a.charAt(i));
}
for(int i=0; i<b.length(); i++) {
bq.offer(b.charAt(i));
}
String result = "";
while(!bq.isEmpty()) {
char var = bq.poll();
if(aq.size() > 0) {
if(aq.peek() == var) {
aq.poll();
result += var;
}
} else {
break;
}
}
if(result.equals(a)) {
return true;
}
return false;
}
}나름 처음 접근은 잘했다. DFS를 써야할 것 같다는 생각이 들었고, 서로 다른 두 문자의 동일성(predecessor 측정)에는 큐를 사용해서 해결하면 좋을 것 같다고 판단했다. 하지만 중간중간 테스트케이스 실패와 최종적으로 Time Exceed 에러까지 내뱉으면서 해결하는데 생각보다 꽤 오랜 시간이 걸렸다.
문제 풀이한 과정을 기록해보면,
Arrays.sort(words, new Comparator<String>() {
@Override
public int compare(String s1, String s2) {
return s1.length() - s2.length();
}
});굉장히 빈번하게 나오는 기능요건인데, 이번에도 구글링으로 복붙했다. Comparator를 사용하면 간단하게 해결할 수 있으므로 이젠 외울 수 있을 것 같다.
문제 요건 상 모든 내용을 하나씩 확인해서 predecessor 여부를 판단해주어야 한다. 처음에는 단순히 dfs함수를 태웠는데, 여기서 Time exceed 오류가 발생했다. 아주 기본적인 것을 빼먹고 있었는데 배열 a가 있고 j < k라 할 때, a[k]가 이미 a[j]의 predecessor라고 한다면 굳이 a[k]를 다시 검색할 필요가 없다는 것이다. (이미 누군가의 predecessor임이 밝혀졌기 때문에)
이를 위해서 boolean[] 형태의 visited 배열을 만들어서 누군가의 predecessor임이 확인되었다면 방문되었음을 표시해주었다. 그리고 dfs로 순환할 때에는 visited가 false(아직 방문되지 않은, 누군가의 predecessor가 되지 않은) 녀석들만 선택적으로 골라 호출하였다. 이 방법을 적용하고 나서 Time exceed 오류는 해결되었다.
큐를 사용하였는데, 처음에는 HashMap을 이용하여 두 문자열 간 일치하는 문자 갯수 차이가 1인 경우를 판별하려고 했다. 하지만 ba와 abc는 predecessor가 되지 않기 때문에 무조건 순서대로 확인해주어야 했다.
두 문자열의 길이 차이가 1인 경우만 선택적으로 비교하였고, 큐에 순서대로 담아 중복되는 경우(순서가 일치하는 경우)에 해당하는 문자만 새롭게 문자열로 구성하여 이것이 길이가 더 짧은(기존에 전달된) 문자열과 동일한지 확인한 후 일치하면 true를 반환해주었다.
더 빠른 시간복잡도를 만들 수 있을 것 같았는데, 내 생각에는 큐에 담아서 하나씩 비교해주는 이 시간 때문에 Runtime에서 더 높은 점수를 받지 못한 것으로 생각된다. 물론 공간복잡도에서도 큐에 해당하는 크기를 계속 만들어줘야하기 때문에 이부분도 손해였다고 생각이 든다.
사실 이 부분이 꽤 애먹은 부분이었다. 처음에는 배열의 끝까지 모두 확인한 다음 만들어진 값을 ArrayList에 담아주려고 했다. 하지만 이렇게 하면 마지막 인덱스까지 이동하지 못하는 경우도 발생하였는데, 해당 인덱스 이후부터 predecessor에 일치하는 원소가 하나도 없을 경우가 이에 해당되었다.
그래서 특정 인덱스를 기준으로 다음 인덱스부터 계속 predecessor를 체크해주되, 만약 이후 일치되는게 하나도 없으면 그때까지 더해진 횟수를 ArrayList에 담아주는 방식으로 변경했다. 결국 predecessor에 일치하는 원소가 있을 때만 dfs를 태우면 되니 오류도 발생하지 않았다.
ArrayList에 저장된 모든 원소들 중 가장 큰 값을 반환해줌으로써 전체 프로그램을 완료하였다.