코딩 테스트_2. 가장 많이 반복되는 문자열들 제거

( 문제 )

 

ex1)

 

abcabcdefabc

위와 같은 문제가 주어질 때,  abc라는 문자열이 3번 반복된다 물론 a도 3번 ab도 3번 기타 다른 집한구들도 반복된다 하지만, 가장 긴 문자열을 가지고 가장 많이 반복되는 문자열은 abc이다. 이럴 때 abc를 삭제하고 남은 문자열을 리턴한다.

결과: def

 

ex2)

"abxdeydeabz"

위와 같은 문자열이 주어질 경우, ex1의 경우로 유추해서 추려내면 ab 2번, de 2번이 나옵니다. 이렇게 조건에 의해 동률일 경우는 둘다 삭제합니다.

결과: xyz

 

---

( 문제 해설 )

 

(목표) 문자열 길이가 1~ 전체길이 // 2까지 획수를 구해야 합니다.

1. for문을 돌면서 문자열 길이에 따라 처음 나올 경우 해당 문자열을 키로 가지는 value를 1로 설정합니다.

2. 순회하면서 같은 키를 만날때마다 +1 해줍니다.

3. 해당 딕셔너리에서 문자열이 가장 길고 크기가 가장 큰 값을 정렬해줍니다.

4. ex2의 경우도 고려하여 key들을 빼주고

 

입력된 문자열을 돌면서 해당 키랑 같은 경우 삭제해줍니다. 삭제할 때 replace매서드를 이용하면 좀 더 쉽게 삭제가 가능합니다

 

---

[ 코드 ]

 

def solution(strs):
    length = len(strs) // 2
    dic = {}
    for i in range(2, length):
        for j in range(len(strs) - (i - 1)):
            tmp = strs[j:j + i]
            # print(tmp, end=" ")
            if len(tmp) < i:
                continue

            if tmp not in dic:
                dic[tmp] = 1
            else:
                dic[tmp] += 1
    # print(dic)

    sorted_dict = sorted(dic.items(), reverse=True)
    sorted_dict.sort(key=lambda x: (x[1], len(x[0])), reverse=True)

    # print(sorted_dict)
    max_length = sorted_dict[0][1]

    delete_str_arr = []
    for st in sorted_dict:
        s, n = st
        if n == max_length:
            delete_str_arr.append(s)
        if n < max_length:
            break

    # print(delete_str_arr)

    s = strs
    for lang in delete_str_arr:
        s = s.replace(lang, "")

    answer = s
    return answer


print(solution("abcabcdefabc"))
# abcabcdefabc
# def

# "abxdeydeabz"
# "xyz"

---

후기

 

코 테날에 이렇게 2문 제 만 풀었어도 면접 기회는 얻었겠죠.

아쉽네요...

하.. 다음에는 3번째 문제 풀이 갑니다.