[ Codility ] PassingCars - python

개념

Lesson 5. Prefix Sums 네 번째 문제

 

문제요약

0,1로만 이루어진 배열A가 입력으로 주어짐. 0은 동쪽으로 가는 차, 1은 서쪽으로 가는 차일때 서로 마주칠 수 있는 케이스는 얼마나 되는지 리턴하는 문제.

예시) [0,1,0,1,1] => (0,1),(0,3),(0,4),(2,3),(2,4) 5개 => 5리턴

 

첫번째 접근( 효율성 고려X )

문제에 충실하게, 앞에서부터 순회하다가 0이 나오면 그 뒤에 있는 1의 개수를 구해 더해나가는 방식

def solution(A):
    cnt = 0
    for i in range(len(A)-1):
        tmp = 0
        if A[i] == 0:
            tmp += A[i+1:].count(1)
        cnt += tmp
    return cnt

 

답은 맞지만 역시 타임아웃. for문에서 O(n), count에서 O(n)해서 O(n**2)

 

두번째 접근( 효율성 고려 but 문제의 조건을 놓침 )

맨 뒤에서부터 순회하면서 1을 세어나가다가 0이 등장하면 더해가던 1의 개수를 결과값에 더해주는 방식(위 방법에서 count함수를 쓰는 대신 더해가는 방식 사용)

def solution(A):
    result = 0
    tmp = 0
    for i in range(len(A)-1,-1,-1):
        if A[i]==0:
            result += tmp
        else:
            tmp += 1
    return result

WRONG ANSWER... 알고보니 문제 중간에 특정 수를 넘어가면 -1을 리턴하라는 조건이 있었는데 이걸 놓친것

 

세번째 접근(통과한 코드 - O(N))

def solution(A):
    result = 0
    tmp = 0
    for i in range(len(A)-1,-1,-1):
        if A[i]==0:
            result += tmp
        else:
            tmp += 1
        if result > 1000000000:
            return -1
    return result

 

참고로 Prefix Sums는 구간합을 의미함. 부분합이 앞에서부터 특정 지점까지의 합을 의미한다면 구간합은 특정 구간의 합이라고 보면 된다. 코딜리티는 시간복잡도와 에러 메시지까지 확인할 수 있어서 알고리즘 개선할 때 도움이 많이 되는 듯.