Consecutive strings

Consecutive strings

이 전까지의 문제가 그냥 믹스 커피였다면 이 문제는 카누 정도 되더군요.

일단 함수의 첫 번쨰 입력으로 연속된 문자열이 담겨 있는 리스트가 오게 됩니다. (다른 언어에선 배열)

그리고 두 번째 입력으로  int형(K) 숫자가 오게 되는데요. 이 두 값을 받아서 연속된 K개의 문자열이 가장 길어지는 경우를 return 해야 합니다.

말로는 어려운데 예를 들면 다음과 같습니다.

["a", "bc" , "def"] , 2 가 들어오게 되면 "bc" , "def" 두 개의 값의 총 길이는 5입니다. 이는 ["a", "bc" , "def"] 에서 2개를 골라 만들 수 있는 가장 긴 문자열 입니다.

단, 앞서 말했듯이 연속되어야 합니다.

그래서 예제로 테스트 해볼 수 있는 다음과 같은 값에서

longest_consec(["it","wkppv","ixoyx", "3452", "zzzzzzzzzzzz"], 3) 만들 수 있는 가장 긴 문자열은 두번째, 세번째 그리고 마지막이지만 연속되지 않았으므로 정답은 "ixoyx3452zzzzzzzzzzzz" 이 됩니다.

아이러니하게도 오늘 오후에 읽었던 책의 챕터가 분할정복이었습니다. 최대부분집합의 수를 구하는 것이 예제로 나와있었는데요. 책 완독이 목표라 좀 대충 읽었더니 기억이 가물가물했었습니다만, 그래도 검색 없이 스스로 짜보기로 하였습니다.

....라고 썼는데요.

다시 보니까 문자열의 길이가 음수가 될리도 없고, 결국 선택할 수 있는 부분집합의 개수는 정해져있기 때문에 그렇게 어려운 문제는 아니였었네요.

어쩐지 갑자기 난이도가 확 올라가서 좀 놀랐었거든요.

일단 풀긴 풀었는데 정말 잘 푼 코드가 아닙니다.

미래의 제가 오늘의 저를 멱살 잡는 소리가 들리네요.

변수명도 아무 의미 없이 손에 가는거 막 갖다 썼구요.

이번주에 작성한 가장 부끄러운 코드 2위에 들 정도라서 (1위는 오늘 푼 쿼드트리) 다음 주 중에 한 번 다시 다듬으려구요 다른 사람들 코드 보고 ㅠㅠ

풀이는 다음과 같습니다.

각 리스트의 문자열의 길이를 갖는 또 다른 리스트를 만들었습니다. ==> ss

그리고 그냥 더해줬어요. n부터 n+k개 까지...

마지막으로 동일한 길이를 갖는 다른 문자열도 뒤에 나올 수 있는데, 문제에서 가장 처음에 등장하는 (가장 긴) 문자열을 고르라고 하여서 그냥 break 해줬습니다.

def longest_consec(strarr, k):
    if k <= 0:
        return ""
    if len(strarr) < k:
        return ""
    if len(strarr) == 0:
        return ""

    ss = map(lambda x: len(x), strarr)
    hh = {}
    n = 0
    max = 0
    flag = True
    while flag:
        ttt = 0
        for t in range(k):
            if n+t >= len(ss):
                flag = False
            else:
                ttt += ss[n+t]
                hh[n] = ttt
        if max < ttt:
            max = ttt
        n += 1

    sr = ""

    for key, value in hh.items():
        if value == max:
            for i in range(k):
                sr += strarr[key+i]
            break
    return sr