Test 관련 끄적 -(2)

아까 못 풀었던 3번 문제를 풀었네요....

3번 문제는 문자열이 연속되게 K번 이상 나오면 0을 출력

아니면 1을 출력하는 문제입니다.

 

rep = ["AFFDEFDEFDEEC", "ABABABABBCCEF", "FFFFFFFFFFFFF", "FCBBBFCBBECBB"]  # [0, 0, 0, 1]
n = 3
k = 2

이렇게 주어질 경우 [0, 0, 0, 1]을 출력하죠,,

FCBBBFCBBECBB

같은 경우 FCBB가 K번 이상 나오지만 연속적으로 나오지 않으므로 1을 출력합니다

다른 경우로 따져봐도 연속으로 나오는 문자열이 없습니다.

 

저는 LRU와 딕셔너리를 조합해서 문제를 풀었습니다.

 

- 알고리즘 띵킹 -

캐시 사이즈를 n값을 놓습니다

캐시 사이즈는 LRU를 구현입니다. 그러면 N만큼 범위 내에서 같은 단어가 나오면 캐시에 안에 있는 문자열은 계속 살아남게 되죠 => 즉, 캐시로 연속을 구현한 것입니다.

그리고 캐시 안에 값이 있으면 dic[문자열] += 1 해주고 처음 나오면 dic[문자열] = 1을 해주는 식으로 처리합니다.

이렇게 순회하면서 dic value값이 k이상이 나오면 더 이상 순회를 종료하고 0을 리턴하면 되는 거죠...

 

코드를 보는 게 더이해가 빠르실 수 있습니다.

 

[ 코드 ]

 

from collections import deque


def solution(replies, n, k):
    answer = [1 for _ in range(len(replies))]

    index = 0
    for rep in replies:
        # rep[i: i + num]
        for num in range(n, len(rep) // 2):
            cache = deque([])
            cacheSize = n
            dic = {}
            isbreak = False
            for i in range(0, len(rep)):
                x = {key:value for key, value in dic.items() if value >= k}

                if x:
                    print(dic)
                    answer[index] = 0
                    isbreak = True
                    break

                print(dic, cache, rep[i: i + num])
                if rep[i: i + num] in cache:
                    cache.remove(rep[i: i + num])
                    cache.append(rep[i: i + num])

                    if rep[i: i + num] in dic:
                        dic[rep[i: i + num]] += 1
                else:
                    if len(cache) >= cacheSize:
                        strs = cache.popleft()
                        del dic[strs]

                    if rep[i: i + num] not in dic:
                        dic[rep[i: i + num]] = 1
                    else:
                        dic[rep[i: i + num]] += 1
                    cache.append(rep[i: i + num])
            if isbreak:
                break
        index += 1

    return answer


rep = ["AFFDEFDEFDEEC", "ABABABABBCCEF", "FFFFFFFFFFFFF", "FCBBBFCBBECBB"]  # [0, 0, 0, 1]
n = 3
k = 2

print(solution(rep, n, k))

---

후기

 

아쉽네요 이문제를 시간 내에 풀고

sql을 한 문제라도 풀었으면 합격했을 거 같은데

결론적으로 두 문제 다 놓쳤으니

탈락할 거 같습니다.