Codility Exercise4

First Unique

 

코드

 

from collections import Counter

def solution(A):

    my_cnt = Counter(A)

    for i in my_cnt.keys():
        if my_cnt[i] == 1:
            return i

    return -1

 

StrSymmetryPoint

 

코드

 

def solution(S):
    if len(S) == 1:
        return 0

    if len(S) % 2 == 0:
        return -1

    for i in range(len(S) // 2):
        if S[i] != S[-(i+1)]:
            return -1

    return len(S) // 2

    return cnt

 

 

TreeHeight

 

 

코드

 

from extratypes import Tree  # library with types used in the task

def solution(T):
    def calculate_height(T):
        if T is None:
            return -1
        else:
            left_height = calculate_height(T.l)
            right_height = calculate_height(T.r)
            return max(left_height, right_height) + 1

    return calculate_height(T)

 

ArrayInversionCount

 

코드

 

이중 for문으로 풀면 범위가 크기 때문에 시간 초과가 난다.

 

병합정렬을 사용해야 한다.

 

def solution(A):
    # 병합 정렬과 인버전 개수 계산을 위한 보조 함수
    def merge_sort_and_count(arr):
        if len(arr) <= 1:
            return arr, 0
        
        mid = len(arr) // 2
        left, count_left = merge_sort_and_count(arr[:mid])
        right, count_right = merge_sort_and_count(arr[mid:])
        merged, count = merge_and_count(left, right)
        
        return merged, count + count_left + count_right
    
    # 병합과 인버전 개수 계산을 위한 보조 함수
    def merge_and_count(left, right):
        merged = []
        count = 0
        i = j = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            else:
                merged.append(right[j])
                count += len(left) - i  # 인버전 개수 계산
                j += 1
        
        merged.extend(left[i:])
        merged.extend(right[j:])
        
        return merged, count
    
    # 병합 정렬과 인버전 개수 계산 수행
    sorted_A, inversions = merge_sort_and_count(A)
    
    # 인버전 개수가 1,000,000,000을 초과하는 경우 -1 반환
    if inversions > 1000000000:
        return -1
    
    return inversions

 

DisappearingPairs

 

코드

 

def solution(S):
    stack = []

    for char in S:
        if len(stack) >= 1 and stack[-1] == char:
            stack.pop()
        else:
            stack.append(char)

    return ''.join(stack)

 

시간초과났던 코드

 

def solution(S):
    if len(S) == 0:
        return S

    my_list = list(S)
    
    for i in range(len(my_list) - 1):
        if my_list[i] == 'A' and my_list[i+1] == 'A':
            index = [i, i+1]
            index.sort(reverse = True)
            for i in index:
                del my_list[i]
            return solution(''.join(my_list))
        if my_list[i] == 'B' and my_list[i+1] == 'B':
            index = [i, i+1]
            index.sort(reverse = True)
            for i in index:
                del my_list[i]
            return solution(''.join(my_list))
        if my_list[i] == 'C' and my_list[i+1] == 'C':
            index = [i, i+1]
            index.sort(reverse = True)
            for i in index:
                del my_list[i]
            return solution(''.join(my_list))
        
    return ''.join(my_list)