이번 포스팅에선 알고리즘사이트인 Codility의 Lesson5 Prifix Sums 문제중 

두번째 문제인 CountDiv 문제에 대해 포스팅 하도록 하겠습니다.

우선 문제를 보시면 다음과 같습니다.

Write a function:

class Solution { public int solution(int A, int B, int K); }

that, given three integers A, B and K, returns the number of integers within the range [A..B] that are divisible by K, i.e.:

{ i : A ≤ i ≤ B, i mod K = 0 }

For example, for A = 6, B = 11 and K = 2, your function should return 3, because there are three numbers divisible by 2 within the range [6..11], namely 6, 8 and 10.

Assume that:

• A and B are integers within the range [0..2,000,000,000];
• K is an integer within the range [1..2,000,000,000];
• A ≤ B.

Complexity:

• expected worst-case time complexity is O(1);
• expected worst-case space complexity is O(1).

문제의 요점은 정수 A,B 그리고 K가 인자값으로 넘어오면 A와 B의 범위 사이에 있는 

수들 중 몇개의 수가 K로 나눌수 있는지, 즉 몇개의 수가 K의 배수인지를 구하여 

리턴하는 간단한 문제입니다.

제가 짠 코드는 다음과 같습니다.

public int solution(int A, int B, int K) {
		
		int rotationCount = 0;
		int count = 0;
		int gap = B-A;
		
		
		for(int i=A; i<=B; i++){
			
			if(i%K==0){
				count++;
				count+=(gap-rotationCount)/K;
				break;
			}
			rotationCount++;
		}
		return count;
	}

사이트에서 테스트를 진행할 경우 정확성도 고려하지만 퍼포먼스(성능) 부분도 평가의 대상이 되기

때문에 불필요한 반복을 최소화 하기위해서, 저는 성능적인 부분을 고려한 코드를 두줄 더 추가해 

주었고 결과는 다음과 같습니다.

이상 간단 알고리즘 문제 풀이 포스팅을 마치도록 하겠습니다.

Posted by Culinary developer