[Codility] 코딜리티 5-2. GenomicRangeQuery (Python)

안녕하세요 ! 오늘도 새로운 문제를 가지고 왔습니다.

 

이전 코드 내용이 궁금하시다면 아래 링크로 이동하시면 됩니다!

코딜리티 이전 글 - 2020/08/05 - [데이터 분석/파이썬] - [Codility] 코딜리티 5-1. CountDiv (Python)

[Codility] 코딜리티 5-1. CountDiv (Python)

---

1. 문제 설명

• S는 'A','C','G','T'로 구성된 string입니다. P와 Q에는 list 형태로 S의 위치를 나타냅니다.
• 'A' : 1, 'C' : 2, 'G' : 3, 'T' : 4, P와 Q 사이의 원소 중에 가장 작은 값을 list로 구성해서 출력하는 것이 문제 입니다.
• 예시 : S ='CAGCCTA', P = [2, 5, 0], Q = [4, 5, 6] (Q 위치의 원소도 포함)
          S[P[0]:Q[0]] = 'GCC', S[P[1]:Q[1]] = 'T', S[P[2]:Q[2]] = 'CAGCCTA'

2. 1차 풀이

• idea : for 문 2개로 구성해서 min_num과 비교하면서 찾기

def solution(S,P,Q):
    result = []
    min_num = 5
    for i in range(len(P)):
        for j in range(P[i],Q[i]+1):
            if S[j] == 'A':
                num = 1
            if S[j] == 'C':
                num = 2
            if S[j] == 'G':
                num = 3
            if S[j] == 'T':
                num = 4
            if num < min_num:
                min_num = num
        result.append(min_num)
        min_num = 5
    return result

3. 1차 결과 (시간복잡도 N*M)

1차 결과

1차 테스트 결과

4. 2차 풀이

• idea : for문을 줄이고, 값이 작은 것부터 있는 지 확인하는 방법을 사용.

def solution(S, P, Q):
    R = []
    for i in range(len(P)):
        A = P[i]
        B = Q[i]
        min_num = 5
        if 'A' in S[A:B+1]:
            num = 1
        elif 'C' in S[A:B+1]:
            num = 2
        elif 'G' in S[A:B+1]:
            num = 3
        elif 'T' in S[A:B+1]:
            num = 4
        if min_num > num :
            min_num = num
        print(S[A:B+1])
        R.append(min_num)
    return R

5. 2차 결과 (시간복잡도 N+M)

2차 결과

• 시간복잡도를 줄이는 작업은 언제나 어려운 것 같습니다.