문제링크

https://app.codility.com/programmers/lessons/3-time_complexity/tape_equilibrium/

풀이

def solution(A):   
    first = A[0]
    second = sum(A[1:])
    res = []
    res.append(abs(first - second))
    for i in range(1, len(A)-1):
        first += A[i]
        second -= A[i]
        res.append(abs(first - second))
    return min(res)

여태 작성했던 방식이 모두 len(A)-1을 안 해서 생긴 오류라는걸 알게됐을때의 허무함...

두쪽으로 나눠야하니 리스트의 끝까지 계산하는 것이 아니라 리스트의 끝의 하나 앞에서 끊어준다.

문제링크

https://app.codility.com/programmers/lessons/3-time_complexity/perm_missing_elem/

풀이

def solution(A):
    l = len(A)
    if l == 0:
        return 1
    else:
        return sum(range(1, l+2)) - sum(A)

처음에는 정렬을 한 후 요소를 2개씩 묶은 후 차이가 1이 아니면 빠진 요소를 찾을 수 있을 것이라 생각하고 작성했는데, 더 간단한 방법이 합을 이용하는 것이었다.

빠진 요소의 길이를 추가한만큼의 합에서 주어진 array의 합을 빼면 어떤 요소가 빠졌는지 나온다.

삽질하다 풀이를 발견해서 다행이다.

문제링크

https://app.codility.com/programmers/lessons/3-time_complexity/frog_jmp/

풀이

import math

def solution(X, Y, D):
    return math.ceil((Y-X)/D)

Y보다 크거나 같게 점프한다고 했으니 올림을 해준다. 처음엔 반올림을 생각했는데 틀렸다해서 올림을 썼다.

문제링크

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

풀이

def solution(A):
    A.sort()
    l = len(A)
    for i in range(0, l, 2):
        # 인덱스의 끝이 답일 때 ex) 2 2 3 3 4
        if i == l-1:
            return A[i]
        if A[i] != A[i+1]:
            return A[i]

문제를 잘못 이해해서 시간을 많이 날렸다. array를 정렬하고 2스텝씩 진행했을때, 맞지 않으면 2스텝씩 묶은 첫번째 요소가 답이 된다. 하지만 만약 [2, 2, 3, 3, 4] 같은 경우는 마지막 요소를 짝을 묶을 수 없으므로 마지막 요소가 정답이 된다. 그래서 if i == l-1 조건문을 넣었다.

시간 복잡도는 O(N), O(N*log(N)) 이 나왔는데 더 줄이고 싶다...🙂 다른 사람의 풀이에서 xor 연산을 사용한 것을 봤는데 저런 두뇌회전.. 커비처럼 삼키고싶음.

문제링크

https://app.codility.com/programmers/lessons/2-arrays/cyclic_rotation/

풀이

def solution(A, K):
    temp = 0
    if len(A) == 0:
        return A
    for _ in range(K):
        temp = A.pop()
        A.insert(0, temp)
    return A

첫번째 시도에서 empty array에 대해 지정을 해주지 않아 통과되지 않았다. 배열의 길이가 0일때 그대로 리턴하도록 설정하니 통과됐다.

문제 링크

https://app.codility.com/programmers/lessons/1-iterations/binary_gap/

풀이

def solution(N):
    bnum = format(N, 'b')
    cnt = 0
    temp = []
    m = 0
    for i in bnum:
        if i == '1' and len(temp) == 0:
            temp.append(i)
        elif i == '0' and temp[0] == '1':
            cnt += 1
        elif i == '1' and temp[0] == '1':
            temp.pop()
            temp.append(i)
            if m < cnt:
                m = cnt
            cnt = 0
    return m

format(N, 'b')은 숫자 N을 이진수로 포맷팅 한다. N = 9 이면 1001이 출력된다.

stack을 사용하여 반복문이 1을 만났을 때 이전까지 카운트한 0의 값을 저장하도록 코드를 구현했는데 풀고 나니 보완할 점이 보인다.

추후에 더 깔끔하게 작성해봐야겠다.