2021-10-23 게시 됨2021-11-04 업데이트 됨개발자 공부 / 코딩테스트6분안에 읽기 (약 949 단어)

코딩테스트 준비하기 w Python - (6) Prefix Sums, Sorting

구간합 알고리즘, 정렬 알고리즘

설명 : https://www.crocus.co.kr/843

부분합 : 길이 N의 배열에서 0 ~ k 까지의 합(0 <= k < N)

구간합 : 길이 N의 배열에서 a ~ b 까지의 합(0 <= a <= b < N)

배열을 순회하면서 인덱스 i까지의 합을 저장한 sum 배열을 계산한다.

a ~ b까지의 구간합은 sum[b] - sum[a] 이다.

Q1. GenomicRangeQuery

문자열 S(길이 N)와 숫자배열 P,Q(길이 M)가 주어진다
문자열 S는 다음 4가지 문자로 이루어져 있다 : A, C, G, T
각 문자는 각각 1, 2, 3, 4의 숫자(=Impact Factor)와 대응된다
find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[K] and Q[K] (inclusive).
숫자배열 P, Q는 각각 start index, end index를 의미한다. S[P[i]] ~ S[Q[i]] 사이의 문자들의 impact factor 중 최소값을 반환하라.

Try 1: https://app.codility.com/demo/results/trainingNCDUH8-QZA/ (66%)

from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
def solution(S, P, Q):
    ret = []
    N, M = len(S), len(P)
    counter = [[0,0,0,0] for _ in range(N)]
    for idx, c in enumerate(S):
        counter[idx] = deepcopy(counter[idx-1])
        counter[idx][ip[c]-1] += 1
    # print(counter)
    for idx in range(M):
        start, end = P[idx], Q[idx]
        if start == end:
            ret.append(ip[S[start]])
        else:
            for i in range(4):
                # print(idx, counter[end][i], counter[end][i])
                if counter[end][i] - counter[start][i] > 0:
                    ret.append(i+1)
                    break
    
    return ret

POINT 문자를 순회하면서 각 문자별로 A, C, G, T가 등장했던 횟수를 저장한다. 등장했던 횟수의 차를 구해서 1번 이상 등장한 minimal impactor를 찾는다.

Analysis summary

The following issues have been detected: wrong answers, timeout errors.

For example, for the input ('AC', [0, 0, 1], [0, 1, 1]) the solution returned a wrong answer (got [1, 2, 2] expected [1, 1, 2]).

Try 2: https://app.codility.com/demo/results/trainingJY9PSW-EVA/ (87%)

from copy import deepcopy
ip = {'A':1, 'C':2, 'G':3, 'T':4}
def solution(S, P, Q):
    ret = []
    N, M = len(S), len(P)
    counter = [[0,0,0,0] for _ in range(N)]
    for idx, c in enumerate(S):
        counter[idx] = deepcopy(counter[idx-1])
        counter[idx][ip[c]-1] += 1
    # print(ip.values().index(0))
    counter.append([0,0,0,0])
    for idx in range(M):
        start, end = P[idx]-1, Q[idx]
        if start == end:
            ret.append(ip[S[start]])
        else:
            for i in range(4):
                if counter[end][i] - counter[start][i] > 0:
                    ret.append(i+1)
                    break
    
    return ret

Almost all same letters 케이스에서 Timeout 발생

Q2. Distinct

https://app.codility.com/demo/results/trainingN5Y9M2-Z67/

N개의 원소로 이루어진 배열 A
배열 A의 원소 종류의 개수를 반환하라

1 2	def solution(A): return len(set(A))

시간 복잡도 : O(N*log(N)) or O(N)

POINT 파이썬 리스트 중복제거하기 : https://blockdmask.tistory.com/543

Q3. MaxProductOfThree

길이 N(3 ~ 100,000)의 배열 A
원소 3개를 곱해서 값이 최대가 되게 하라

Try 1: https://app.codility.com/demo/results/trainingGYUQBS-SBY/ (44%)

1
2
3

def solution(A):
    A.sort()
    return A[-1]*A[-2]*A[-3]

단순히 정렬해서 제일 큰 3개를 곱해서 반환
당연히 답이 아녔다
음수가 존재할 수 있으므로 음수 * 음수 * 양수 의 케이스로 최대값이 될 수 있다

Try 2: https://app.codility.com/demo/results/training7RGBFS-7K8/ (100%)

def solution(A):
    A.sort()
    if A[0] < 0 and A[1] < 0:
        return max(A[0]*A[1]*A[-1], A[-1]*A[-2]*A[-3])
    else:
        return A[-1]*A[-2]*A[-3]

Q4. Triangle

https://app.codility.com/demo/results/trainingNGU2KK-WYV/

3개의 값 a,b,c에 대해 a+b > c, b+c > a, a+c > b 이면 값 a,b,c는 triangular 하다고 한다.
주어진 길이 N(3 ~ 100,000)의 배열 A에 대해 triangular한 값이 존재하는경우 1을, 존재하지 않는경우 0을 반환하라

def solution(A):
    A.sort()
    for i in range(2,len(A)):
        a, b, c = A[i-2], A[i-1], A[i]
        abc = a+b+c
        if abc > 2*a and abc > 2*b and abc > 2*c:
            return 1
    
    return 0

POINT : 주어진 조건을 만족하는 a,b,c 는 다음의 조건 역시 만족하게 된다 => a+b+c > 2a, a+b+c > 2b, a+b+c > 2c. 배열 A를 정렬한 후 순회하며 이 조건을 만족하는 3개 페어가 있는 경우 1을 반환한다.

CHECK : A=[1, 2, 3, 4, 5] 의 배열에서 [3, 4, 5] 만 순회하기

1 2	for i in range(2,len(A)): print(i) # Output : 2, 3, 4

range(start, end) : start 인덱스는 포함, end 인덱스는 미포함