Codility - CountDiv [Python]

😅 문제 

🤔 문제 상황 

- 문제의 범위가 너무 커서 단순히 O(N)으로 정의하면 안된다. 첫번째 풀이로는 O(B-A)인데 이는 최대 20억이 될 수 있으므로 시간 초과가 된다. 문제의 상황이 값 자체를 찾는 것이 아니라 개수를 찾는다는데 포인트를 잡아야 된다.

 

 

🧐 해결 전략 

- divisable 여부를 찾는 것이므로 시작값과 끝 값으로 개수를 계산한다. 단, A가 K로 나눠 떨어지는지 여부에 따라 1개 차이가 날 수 있다.

 

🎰 코드 

# O(B-A)
 
def solution1(A, B, K):
    ret = 0
    for dividend in range(A, B+1):
        if dividend % K == 0:
            ret += 1
    return ret
 
#O(1)
 
def solution2(A, B, K):
    quotientA = A // K
    remainderA = A % K
    quotientB = B // K
    return quotientB - quotientA + 1 if remainderA == 0 else quotientB - quotientA
 
 

 

🧙‍♂️ 해설

 

처음에는 단순히 문제 상황을 시뮬레이션 하려고 해서 O(N)이면 충분하다고 생각했지만 주어진 조건을 계산해보지 않았다.문제의 범위가 20억이므로 O(N), 정확히는 O(B-A)로는 부족했다. 주어진 조건에서 시작 값이 나누어 떨어질 경우와 아닐 경우에 1개 개수 차이가 나는 것을 후에 확인했다.

 

 

📈 새로 학습한 것 & 실수 

- 기계적으로 문제 상황을 시뮬레이션 하는 것을 조심해야한다. O(N)이면 충분하다고 생각하는 고정관념이 생겼다. 상황에 따라 상수 시간도 가능함을 인지해야한다. 

 

- 문제 상황이 그 값 자체를 찾는 것인지, 개수를 찾는 것인지를 구별할 필요가 있다.

 

출처 - https://app.codility.com/programmers/lessons/5-prefix_sums/count_div/