Python을 사용한 코드 작성의 PassingCars

다음 주 첫 인터뷰에서 코딩에 어려움이 있습니다. HR은 코딩 챌린지 플랫폼으로 Codility를 사용할 것이라고 말했습니다. 나는 Codility Lessons을 사용하여 연습 해왔다.Python을 사용한 코드 작성의 PassingCars

내 문제는 내가 정확도에서 매우 높은 점수를 얻지 만, 시간 복잡도를 측정하는 성능 점수는 끔찍합니다 (종종 0 %가 됨).

다음은 질문 : https://app.codility.com/programmers/lessons/5-prefix_sums/passing_cars/

내 코드는 다음과 같습니다 그것은 O (N) 있어야하는데

def solution(A): 
    N = len(A) 
    my_list = [] 
    count = 0 
    for i in range(N): 
     if A[i] == 1: 
      continue 
     else: 
      my_list = A[i + 1:] 
      count = count + sum(my_list) 
    print(count) 
    return count

그러나 광산은 O입니다 (N ** 2).

어떻게하면 O (N) 시간 복잡도로 문제를 해결할 수 있습니까?
일반적으로 알고리즘 질문을 볼 때 어떻게 접근 할 수 있습니까?

출처

2017-12-31 Jun Jang

0을 찾을 때마다 전체 배열을 합쳐서는 안됩니다. 그게 O (n^2)가됩니다. 대신에 발견 된 모든 제로 한 다음 각각에 대해 +1을 줄 것이다 참고 :

def solution(A): 
    zeros = 0 
    passing = 0 
    for i in A: 
     if i == 0: 
      zeros += 1 
     else: 
      passing += zeros 
    return passing

출처

2017-12-31 22:55:27

이 도와 주셔서 너무 감사합니다! 일반적으로, 당신은 어떻게 그런 화려한 해결책을 생각해 내는가? 나는 내가 100 시간을 쓰더라도 해결책을 생각해 낼 수 있다고 생각하지 않는다. 그것은 연습에 의한 것입니까? –

많은 연습. 그러나 O (n)을 원한다면 각 요소를 한 번만 볼 필요가 있습니다. 당신에게는 항상 좋은 출발점 인 해결책이있었습니다. 그런 다음 작업 솔루션을보고 각 요소를 여러 번 볼 필요가없는 방법을 확인하십시오. –

나는 본다. 고맙습니다. –

Python을 사용한 코드 작성의 PassingCars

답변

관련 문제