[Codility] 코딜리티 5-4. PassingCars (Python)

안녕하세요! 오늘은 여러 개의 문제를 업로드하고 있습니다!

오늘부터는 결과 말고 코드만 올리도록 하겠습니다!

 

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

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

[Codility] 코딜리티 5-3. MinAvgTwoSlice (Python)

---

1. 문제 설명

• 0은 동쪽을 향해가는 차, 1은 서쪽으로 가는 차를 말합니다.
• 문제 결과로는 동쪽으로 향해가는 차들이 서쪽으로 가는 차량을 몇 번 마주치게 되는지 총합을 출력하면 됩니다.
• A = [0, 1, 0, 1, 1]이라고 했을 때, 0이 출력되면 그 뒤로 나오는 1의 개수(3) + 2번째 0이 출력된 뒤로 나오는 1의 개수(2)인 5를 출력하면 됩니다.
• 그리고 출력할 값이 1000000000보다 크면 -1을 출력합니다.

2. 1차 풀이 (시간 복잡도 : N**2)

• idea : A에서 0을 찾으면, 그 뒤로 1의 개수가 나올 때마다 count 해서 count값을 출력
• Task : 50, correctness : 100, performance : 0, 시간복잡도 : N**2

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

3. 2차 풀이 (시간 복잡도 : N)

• idea : basket이라는 리스트를 생성해서 0번째 인덱스에는 0의 개수, 1번째 인덱스에는 0과 0 사이 1의 개수를 넣는 방식을 활용
• Task : 100, correctness : 100, performace : 100, 시간복잡도 : N

def solution(A):
    Sum = 0
    basket = [0]*2 # basket[0] : 0의 갯수, basket[1] : 1의 갯수(0과 0사이)
    for i in A:
        if i == 0 :
            basket[0] +=1
            basket[1] = 0
        elif i == 1 :
            basket[1] =1
            Sum += basket[0] * basket[1]
    if Sum > 1000000000:
        Sum = -1
    return Sum