2014 - Longest Subsequence Repeated k Times
info
- 문제 보기: 2014 - Longest Subsequence Repeated k Times
- 소요 시간: 25분 25초
- 풀이 언어:
java
- 체감 난이도: 3️⃣~4️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
완전탐색
bfs
풀이 코드
info
- 메모리: 45420 KB
- 시간: 535 ms
class Solution {
String s;
int k;
boolean hasK(String ss) { // ss: subsequence
int i = 0; // index of ss
int cnt = 0; // count of ss appearance in s
char[] ssArr = ss.toCharArray();
for (char ch : s.toCharArray()) {
if (ch == ssArr[i]) {
++i;
if (i >= ssArr.length) {
i = 0;
++cnt;
if (cnt == k) return true;
}
}
}
return false;
}
public String longestSubsequenceRepeatedK(String s, int k) {
this.s = s;
this.k = k;
String ans = "";
Deque<String> dq = new ArrayDeque<>();
dq.add("");
while (!dq.isEmpty()) {
String cand = dq.poll();
for (char ch = 'a'; ch <= 'z'; ++ch) {
String nCand = cand + ch;
if (hasK(nCand)) {
ans = nCand;
dq.add(nCand);
}
}
}
return ans;
}
}
풀이 해설
문자열 s
에서 k
번 등장하는 subsequence를 구하는 문제이다. (substring 아님)
경우의 수가 상당히 우려되지만 문제의 제약 조건이 아주 절묘하게 설정되어 있어서,
bfs로 완탐을 돌려도 TLE가 발생하지 않는다(!)
bfs로 level-by-level traversal을 수행하면 되는데, 다만 시간복잡도 계산 면에서 좀 부조리한 느낌이 있다.
✏️ 문제 구조화하기
발상을 이런식으로 가야 한다.
- subsequence 문자열
ss
의 등장 빈도가k
인지 계산하는 로직 구상 ss
를 구성하는 로직 구상
1번은 풀이에서의 hasK
함수 로직에 해당하고, 비교적 발상하기 쉽다.
그러나 2번에서 이리저리 최적화 기법을 생각하다보면 꽤나 시간이 흐르게 된다.
그 이유는 정답이 최대 길이의, lex-largest 해야 한다는 조건이 있기 때문이다.
for: z -> a 순으로 순회
for: 최대길이 ~ 최소길이 순으로 순회
맨 처음엔 상단의 방식으로 순회하는 것을 고민해보았는데, 의미가 없다.
z일때 길이 x인 후보를 찾았는데, 그 다음 순회인 y에서 x+1 길이의 후보를 찾을 수도 있기 때문이다.
for: 최대길이 ~ 최소길이 순으로 순회
for: z -> a 순으로 순회
아 그럼 이렇게 하면 되겠네! 싶어 두번째 발상으로 시도해보지만, 코드 짜보면 z -> a 순회 부분에서 막힌다.
z로 시작하는 최대 길이 문자열로 init해야 하고, 순회하면서 하나씩 잘라 다른 문자 붙여야 하고... 이게 맞나 싶어진다.
그래서 결국엔 완탐으로 회ㅋ귀ㅋ... 하게 되는데
여기서 시간복잡도가 걱정되기 시작한다.
🕗️ 완탐의 시간복잡도는?
사실 ss
의 길이를 len이라고 할 때, 시간복잡도는 hasK
제외 완탐만 따지자면 이다.
이제 여기서 hasK
로직까지 들어가면 인데 슬슬 TLE이 각이 서기 시작한다.
하지만 지문에서 n < k * 8
이라는 조건을 보자.
이는 len * k <= n
이라는 또다른 조건을 생각해 볼 때, len * k <= n < k * 8
로 연립할 수 있으므로
모든 항에 k
를 나눠서 (k > 0 이므로 가능)
len <= n / k < 8
이라는 수식으로 정리할 수 있게 된다.
즉, subsequence 길이(len)는 n
과 k
를 어떻게 지지고볶든 최대 7임을 알 수 있고
따라서 hasK
제외 시간복잡도는 80억인데 여기서 또 어? 싶지만
hasK
를 통한 가지치기가 이루어지기에 pruning 덕분에 엄청나게 경우의 수가 줄어들어서 시간 내 통과하게 된다.
특히, a~z 전체 말고 각 문자별 카운팅해서 k 이상인 것들만 추리면 탐색 범위는 더더욱 줄어들게 된다.
😮 결론: 계산적으로 알기 어렵기에 감으로 알아야 함
메모
- 시간복잡도 계산때문에 hard 인듯?
- subsequence를 구성할 문자를 추려놓으면 최소 절반 이상의 수행시간이 단축되는듯 하다.