[codility] Lesson 4-4) PermCheck 5-1) countDiv 5-2) GenomicRangeQuer

📌 4-4) PermCheck

1부터 N까지의 +1 씩 증가하는 수열인지 아닌지 판별하여라 

 

처음풀이

def solution(A):
    A.sort()

    if len(A)>1:
        for i in range(len(A)-1):
            if A[i]+1==A[i+1]:

                ans=1
            else:
                ans=0
                break
        return ans
    else:
        if A[0]==1:
            return 1
        else:
            return 0

A의 배열을 뒤의 값과 비교하고

그 값과 1차이 날때만 정답 아니면 0

A배열 인자가 하나라면 1일때만 정답 아니면 0 이라는 로직으로 풀었지만..

 

 

히든 테케를 유심히 읽어보니 

[2,3,4,5...] 1이 아닌 수로 시작하는 연속수열

[1,1] 더블 두개가 안잡히는걸 확인하고 

 

 

정답 풀이

def solution(A):
    A.sort()
    if A[0]==1:
        if len(A)<2:
            return 1
        else:
            for i in range(len(A)-1):
                if A[i]+1==A[i+1]:
                    ans=1
                else:
                    ans=0
                    break
            return ans
    else:
        return 0

이렇게 바꿨다.

문제를 꼼꼼히 읽어야 한다는 교훈을 얻었다. 

 

 

 

 

다른 풀이

def solution(A):
    if max(A) != len(A) or len(set(A)) != len(A):
        return 0
    return 1

A = [1,2,3,4,5,6] 

최대값 = 6 

길이 = 6 

이므로 상위 조건들을 이용해 간단하게 처리가 가능했다.

 

---

📌 5-1 ) CountDiv

A와 B 사이에 잇는 수들 중 K로 나눠지는 수의 개수를 구하라!

잉? 모야 쉽네 라고 생각했지만. 역시나 코딜리티는 시간복잡도를 그냥 주지 않았다.

 

1차시도 (시간 초과)

def solution(A, B, K):
    cnt=0
    for i in range(A,B+1):
        if(i%K==0):
            cnt+=1
    return cnt

사실 마음으로 이렇게 절대 통과 못할 거 알고 있었지만 일단 해본거였다.ㅎㅎ

원하는 시간 복잡도는 O(N) 그러나 나는 O(N^2) 고치자!!!!

여기서 O(B-A)는 arr[a:b] 와같이 

0 < a,b < n 이라는 가정에하에 표기한 것이고 O(N)이라고 보면 된다.

2차 시도(틀린 답)

def solution(A, B, K):
    if A<=K:
        A=K
    namA =A%K
    namB =B%K
    ans=B-A+1-namA-namB
    ans= ans//K
    return ans+1

그다름으로 생각해본건 수학적으로 여러가지 테스트케이스를 생각해보며 만든 공식

1) A가 K보다 작으면 의미 없으므로 A를 K부터 시작하게 만들고

2) 각각의 나머지를 구한다음

3) 그 사이에 있는 개수중에서 나머지만큼을 빼고 나누면 답!

 

잘못생각했다~~ 나머지가 아니라 몫이 몇개씩 들어있는지 개산해서 빼면 되는 거였다..

 

다른풀이

def solution(A, B, K):

    mocA = A//K
    namA =A%K
    mocB = B//K
    cnt = mocB-mocA

    if namA==0:
        cnt+=1
        
    return cnt

 수학적인 계산이 필요햇던 문제!

 

---

📌 5-2) GenomicRangeQuery

배열 두가지가 주어질 때 유전적최소값(?)을 풀어보기

 

처음 풀이

def solution(S, P, Q):
    dObj = {'A':1,'C':2,'G':3,'T':4}
    ansArr =[]

    for i,j in zip(P,Q):
        if i==j:
            ansArr.append(dObj[S[i]])
        else:
            tempArr=[]
            for k in S[i:j]:
                tempArr.append(dObj[k])
            ansArr.append(min(tempArr))
    return(ansArr)

1) P,Q 를동시에 돌면서 두가지값을 빼서

2) S 에서슬라이싱을한다.

3) 그 슬라이싱 안에서 돌면서 dObj와 비교해 최소값을 찾는다

4)  최소값 배열 return 

 

 

이 로직의 잘못된 점은 두가지이다.

1.slice를 i ~j+1 까지 해야한다

2. 시간 복잡도 실패 

제한 시간 복잡도는 O(nm)이었는데 이중 for문을 만들어 O(n^2)이 되었다.

 

 

개선 풀이

def solution(S, P, Q):
    dObj = {'A':1,'C':2,'G':3,'T':4}
    ans =[]

    for i,j in zip(P,Q):
        minNum=5
        if i==j:
            ans.append(dObj[S[i]])
        else:
            if 'A' in S[i:j+1]:
                num = 1
            elif 'C' in S[i:j+1]:
                num = 2
            elif 'G' in S[i:j+1]:
                num = 3
            elif 'T' in S[i:j+1]:
                num = 4
            
            if minNum > num:
                minNum = num
            ans.append(minNum)

    return(ans)

for문을 하나 제거하고 슬라이싱을 고쳐주었더니 답 등장!!!

시간의 효율성을 생각해야 겠다는 교훈을 얻었다.