코딜리티를 이용한 코딩테스트 준비 (lesson 5~)

코테 날짜가 임박해서 lessen 5부터는 각 레슨마다 마지막 문제를 풀어보기로 했다. 

 

핵심

• dict를 사용하는 것은 시간 소비가 큼. -> 지양할 것.
• 리스트 정렬 sorted, sorted(reverse=True)

GenomicRangeQuery

# 구간별로 분할되는 배열에서 가장 작은 값 출력하는 문제. 
# 시간 복잡도 O(NXM), 정답률 62%

def solution(S, P, Q):
    dna = {'A': 1, 'C':2, 'G':3, 'T':4}
    new_s = [dna[i] for i in S]
    ans = list()
    for p, q in zip(P, Q):
        ans.append(min(new_s[p:q+1]))
        # print(new_s[p:q+1] ,p, q)
    return ans


# min을 없애고 if else 구문으로 시간 복잡도를 줄임. 
# 기존의 dict를 이용한 변환 코드도 제거하여 new_s를 생성하는 것에 대한 시간 소비를 없앰.
# 시간 복잡도 O(N+M), 정답률 100%

def solution(S, P, Q):
    ans = list()
    for p, q in zip(P, Q):
        new_s = S[p:q+1]
        if 'A' in new_s: ans.append(1)
        elif 'C' in new_s: ans.append(2)
        elif 'G' in new_s: ans.append(3)
        else: ans.append(4) 
    return ans

 

MinAvgTwoSlice

#배열 내 계산 가능한 모든 평균값 중 가장 작은 값을 출력하는 문제. 
#prefix sum(구간 합 알고리즘)을 제대로 활용하는 문제는 아닌 것 같다. 
#chat GPT가 구한 답, 정답률 100%

def solution(A):
    n = len(A)
    min_avg = (A[0] + A[1]) / 2.0
    min_idx = 0

    for i in range(2, n):
        avg = (A[i-2] + A[i-1] + A[i]) / 3.0
        if avg < min_avg:
            min_avg = avg
            min_idx = i-2
        avg = (A[i-1] + A[i]) / 2.0
        if avg < min_avg:
            min_avg = avg
            min_idx = i-1

    return min_idx

위 코드에 대한 쉬운 설명은 아래 링크를 참고 하면 된다. 

https://cheolhojung.github.io/posts/algorithm/Codility-MinAvgTwoSlice.html

[Codility] MinAvgTwoSlice 문제 풀이 | jcheolho

 

Triangle

# 삼각형이 되는 조건을 만족하는 triplet이 존재하는 지 탐색하는 문제.
# 시간 복잡도 O(N log N), 정답률 100%

def solution(A):
    A = sorted(A)
    for index in range(len(A)-2):
        # if A[index] < A[index+1] + A[index+2]: ALWAYS TRUE
        # if A[index+1] < A[index] + A[index+2]: ALWAYS TRUE
        if A[index+2] < A[index] + A[index+1]: return 1
    return 0

 

Nesting

# '(' 또는 ')'로 이루어진 문자열에서 () 쌍이 완전하게 잘 존재하는지 판별하는 문제.
# 시간 복잡도 O(N), 정답률 100%

def solution(S):
    left, right = 0, 0
    for s in S:
        if s == "(": left += 1
        else: right += 1
        if left < right : return 0
    if left != right : return 0 
    return 1

 

Fish

# 문제가 길어서 이해하기에 시간이 걸렸던 fish task
# chat GPT 이용.
# 시간 복잡도 O(N), 정답률 100%

def solution(A, B):
    downstream_fish = []
    alive_fish = 0
    
    for i in range(len(A)):
        if B[i] == 1:  # downstream fish
            downstream_fish.append(A[i])
        else:  # upstream fish
            while len(downstream_fish) > 0:
                if downstream_fish[-1] > A[i]:  # downstream fish eats upstream fish
                    break
                else:  # upstream fish eats downstream fish
                    downstream_fish.pop()
            else:  # upstream fish survives
                alive_fish += 1
    
    return alive_fish + len(downstream_fish)

 

 

MinMaxDivision

# 배열 A 내 K개의 부분 배열로 분할할 때, 분할 된 배열의 최대합으로 나올 수 있는 가장 작은 수를 구하는 문제
# 가장 작게 분할할 때, 최대합은 max(A)가 되고, 가장 크게 분할할 때, 최대합은 sum(A)가 된다.

# 시간 복잡도 O(N log(N+M)), 정답률 100%

def resulting_blocks(K, A, target_sum):
    """Count blocks that have a sum at most equal to target_sum."""
    result, temp_sum = 0, 0
    for number in A:
        if temp_sum + number > target_sum:
            result += 1
            temp_sum = number
        else:
            temp_sum += number
    result += 1
    return max(result, K)

def solution(K, M, A):
    """Solution method implementation."""
    # initializations
    upper, lower, result = sum(A), max(A), -1
    # main binary search loop
    while upper >= lower:
        # get mid point
        mid = (upper + lower) // 2
        # split array into blocks summing up the mid point       
        blocks = resulting_blocks(K, A, mid)
        
        # the sweet spot's above mid point       
        if blocks > K:
            lower = mid + 1
        # found a minimal large sum candidate
        # seek an even lower candidate in [lower, mid-1]
        elif blocks == K:
            result = mid if result == -1 else min(result, mid)
            upper = mid - 1
    return result

참고 설명은 아래 링크를 참고한다. 

https://interviewnoodle.com/codility-algorithm-practice-lesson-14-binary-search-algorithm-task-1-minmaxdivision-a-python-f3d151b102a5

Codility Algorithm Practice Lesson 14: Binary Search Algorithm, Task 1: MinMaxDivision— a Python…