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

코딩테스트 준비하기 w Python - (5) 복습하기

Codility 문제들 중 이미 풀었던 문제들을 파이썬으로 다시 한번 정리해보기.

Q1. Binary Gap(73%)

https://app.codility.com/demo/results/trainingV8865J-GD2/

def solution(N):
    # write your code in Python 3.6
    maxcnt, cnt = -1, 0
    flag = 0

    while True:
        if N == 0:
            break

        c = N%2
        if c == 1 and flag >= 1:
            flag = 2
            if cnt > maxcnt:
                maxcnt = cnt
            cnt = 0

        elif c == 1 and flag == 0:
            flag = 1

        else:
            cnt += 1

        # print(N, c, flag, cnt, maxcnt)
        N = N//2
    
    if flag == 2:
        return maxcnt
    else:
        return 0

Q2. Cyclic Rotation

Q3. Odd Occurrences In Array

https://app.codility.com/demo/results/trainingGE7AE2-NNT/

각 값은 0 - 1,000,000,000
배열은 최대 1,000,000 개의 원소 가질 수 있다.
배열에서 짝이없는 값 1개 찾아내기
맨처음 생각한게 정렬해서 앞에서부터 훑는거긴 했다. 느릴것같다 생각했는데 이게 맞는듯?

def solution(A):
    A.sort()
    for i in range(0,len(A)-1,2):
        if A[i] != A[i+1]:
            return A[i]

    return A[-1]

POINT 전체를 다 확인하는게 아니고 하나씩 건너뛰면서 확인함으로서 시간 줄이기

Q4. Frog Jump

https://app.codility.com/demo/results/trainingXGHMFE-PR5/

x, y, d 가 주어진다. x -> y 까지 d씩 뛸때 점프횟수

def solution(X, Y, D):
    ret = (Y - X) // D
    if (Y - X) % D > 0:
        return ret + 1
    else:
        return ret

Q5. Perm Missing Element

https://app.codility.com/demo/results/training9K34BE-NJY/

길이 N의 배열 A가 주어진다. N의 범위는 0 ~ 100,000
배열의 모든 값은 distinct 하다
배열 A에는 1~N+1 의 값이 들어있다. 빠진 값 하나를 찾아라

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

    A.sort()
    for i in range(len(A)-1):
        if A[i+1] - A[i] != 1:
            return A[i]+1

    if A[-1] == len(A):
        return A[-1]+1
    else:
        return A[0]-1

POINT 값을 정렬후 순회하면서 이전값과 1 차이나는지 비교. 정답이 시작, 끝에 있는경우와 empty array에 대해 처리주의

=> [1,3], [1,2], [2,3], [] 의 각 케이스의 예상 정답은 2, 3, 1, 1 이다

Q6. Tape Equilibrium

https://app.codility.com/demo/results/trainingXB9X9R-M53/

배열이 주어진다. 배열을 2개 파트로 나눴을때 그 차이가 최소가 되는 지점을 찾아 그 값을 반환하라.

def solution(A):
    # write your code in Python 3.6
    sumarr, mindiff = [0], 2e9
    for i, a in enumerate(A):
        # print(i, a, sumarr)
        sumarr.append(sumarr[i]+a)

    del sumarr[0]
    totsum = sumarr[-1]
    # print(sumarr, totsum)
    for s in sumarr[:len(sumarr)-1]:
        diff = abs(2*s - totsum)
        # print(diff)
        if diff < mindiff:
            mindiff = diff

    return mindiff

POINT 배열에 대한 합 배열을 만든다. 합 배열을 순회하며 | arr[i] - (sum - arr[i]) | 의 최소값을 찾는다.

Q7. PermCheck

https://app.codility.com/demo/results/training5MS7E7-SQJ/

def solution(A):
    # write your code in Python 3.6
    A.sort()
    for i in range(len(A)):
        if A[i] != i+1:
            return 0

    return 1

Q8. MaxCounters

길이 M 배열 A와 구분값 N이 주어진다.
A의 원소는 1 ~ N+1 의 값으로 이루어져 있다.
A의 값 K가 1 ~ N이면 K번째 값에 +1
A의 값 K가 N+1이면 전체값을 이때까지의 최대값으로 리셋

POINT Max Counter 연산 후에도 전체 배열의 값이 아닌 해당 위치의 값만 업데이트(A[i] += (1+ prevmax)) 한다. 업데이트 끝나고 최종 Max Value보다 작은 값들은 Max Value 로 다시 업뎃한다. => O(NM) 을 피하기 위해 O(2N) 의 알고리즘 짜는 것이 핵심

Try 1 https://app.codility.com/demo/results/training2DCTJV-ZHJ/ (33%)

def solution(N, A):
    # write your code in Python 3.6
    counter = [0]*N
    prevmax, curmax = 0, 0
    for a in A:
        if a <= N:
            c = counter[a-1]
            if c < prevmax:
                counter[a-1] += prevmax + 1
            else:
                counter[a-1] += 1
              
            if counter[a-1] > curmax:
                curmax = counter[a-1]
        else:
            prevmax = curmax
        # print(a, curmax, prevmax, counter)

    for i in range(N):
        if counter[i] < prevmax:
            counter[i] = prevmax
    
    return counter

현재값이 이전 max보다 작을때 현재값은 (counter[a-1] + prevmax + 1) 이 아닌 (prevmax + 1) 이다.

Try 2 다듬은 버전(100%)

def solution(N, A):
    # write your code in Python 3.6
    counter = [0]*N
    prevmax, curmax = 0, 0
    for a in A:
        if a <= N:
            if counter[a-1] < prevmax:
                counter[a-1] = prevmax

            counter[a-1] += 1    
            curmax = max(curmax, counter[a-1])            
        else:
            prevmax = curmax
        # print(a, curmax, prevmax, counter)

    for i in range(N):
        if counter[i] < prevmax:
            counter[i] = prevmax
    
    return counter

Q9. MissingInteger

길이 N의 배열 A(N은 1~100,000). 배열의 각 값은 -1,000,000 ~ 1,000,000 이다.
배열에 없는 0보다 큰 가장 작은 양수를 찾아라

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

def solution(A):
    
    A.sort()
    
    # max value is smaller than 0
    # min value is bigger than 1
    if A[-1] <= 0 or A[0] > 1:
        return 1
    
    for i in range(1,len(A)):
        # print(i, A[i], A[i-1])
        if A[i] > A[i-1]+1:
            return A[i-1]+1
    
    return A[-1]+1

음수와 양수가 섞인 케이스에 대해 고려되지 않음

[-44, -3, 4, 5, 2, 6] => 1
[-4, -3, 0, 1, 2, 3] => 4
[-4, -3, 0, 1, 1, 1, 2, 3, 6, 7] => 4
[3, 4, 5, 6] => 2

Try 2. https://app.codility.com/demo/results/trainingP88B9D-6GM/ (100%)

def solution(A):
    
    A.sort()
    curmin = 1
    for a in A:
        if a <= 0:
            continue
        
        if curmin == a+1:
            continue
        elif curmin == a:
            curmin += 1
        else:
            return curmin
    
    return curmin

현재의 가장 작은 양수값(curmin) 을 저장해두고 정렬된 배열 순회. 해당값 없으면 curmin 반환한다