[ Codility ] CountDiv - python

개념

Lesson 5. Prefix Sums 첫 번째 문제

 

문제요약

입력으로 정수 A, B, K가 주어졌을 때 정수 A부터 정수 B(를 포함해서) 사이에 있는 정수들 중 K로 나누어 떨어지는 수들의 총 개수를 리턴하라 

 

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

문제에서 풀이한 방식 그대로 코드 구현

def solution(A, B, K):
    sn = A # 01 starting number를 A로 설정
    cnt = 0
    while sn<=B: # 02 sn이 B가 될 때까지 
        if sn%K==0:
            cnt += 1 # 03 나누어 떨어질 경우 카운트 올리기
        sn += 1 # 04 sn에 1씩 더하기
    return cnt

while문을 B-A만큼 반복하기 때문에 O(B-A), 틀린 풀이는 아니지만, 효율성 문제로 50%의 확률(타임아웃 에러)

 

두번째 접근(효율성 고려O, 통과한 코드) 

생각해보니 A~B 사이에 K의 배수가 몇개나 있는지만 세면 되는 문제였음(마지막에 시작값이 K배수인지만 고려해서 +1)

def solution(A, B, K):
    s = A//K
    l = B//K
    return l-s+ (1 if A%K==0 else 0)

 

코드 리뷰

일단 생각했던 풀이방식대로 코드를 정확하고 순차적으로 구현하는 것도 중요하지만, 문제를 제대로 파악하면 더 간단하게 풀 수 있는 방법이 있다. 뿌듯한 O(1).