Skip to main content

2014 - Longest Subsequence Repeated k Times

info

풀이 키워드​

스포주의

완전탐색 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을 수행하면 되는데, 다만 시간복잡도 계산 면에서 좀 부조리한 느낌이 있다.


✏️ 문제 구조화하기​

발상을 이런식으로 가야 한다.

  1. subsequence 문자열 ss의 등장 빈도가 k인지 계산하는 로직 구상
  2. 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 제외 완탐만 따지자면 O(26len)O(26^{len})이다.

이제 여기서 hasK 로직까지 들어가면 O(26len×n)O(26^{len} \times n) 인데 슬슬 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 제외 시간복잡도는 O(267)≈O(26^7) \approx 80억인데 여기서 또 어? 싶지만

hasK를 통한 가지치기가 이루어지기에 pruning 덕분에 엄청나게 경우의 수가 줄어들어서 시간 내 통과하게 된다.

특히, a~z 전체 말고 각 문자별 카운팅해서 k 이상인 것들만 추리면 탐색 범위는 더더욱 줄어들게 된다.

😮 결론: 계산적으로 알기 어렵기에 감으로 알아야 함


메모​

  • 시간복잡도 계산때문에 hard 인듯?
  • subsequence를 구성할 문자를 추려놓으면 최소 절반 이상의 수행시간이 단축되는듯 하다.