이번 포스팅에선 알고리즘사이트인 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

이번 글을 통해 알고리즘 테스트 사이트인 Codility 에 나오는 

Lesson5 passing cars 알고리즘에 관해서 포팅해보도록 하겠습니다.

관심이 있으신 분들은 사이트를 참고해 주시면 되겠습니다. Codility

Lesson5는 Prefix Sums part 입니다.

저는 Lesson5에 PassingCars 알고리즘을 풀어보았습니다.

우측의 view를 클릭하면 문제의 지문을 미리 볼 수 있습니다.

start 버튼을 클릭하면 이름과 이메일을 묻는 창이 뜹니다.

새로운 알고리즘이 나올때, 혹은 직업추천을 해준다고 하는군요.

정보를 입력하고 넘어가면 문제수와 제한시간정보가 나옵니다.

알고리즘 작성을 위한 페이지 입니다.

좌측이 알고리즘, 우측 상단이 코드를 입력하는 부분, 하단은 콘솔창 입니다.

지원되는 언어는 C, C++, C# Java, Pascal, Python, C# 입니다. 

언어를 변경하면 언어에 맞게 code 입력창과 지문이 해당 언어에 맞게 조금씩 변경됩니다.

코드가 다 작성된 후 언어를 변경하면 수정해야 하니 미리 자신에게 맞는 언어를 

선택하시면 되겠습니다.

지문내용을 보면 

다음의 상황에서는 5쌍의 차가 나오므로 숫자 5를 리턴하는 알고리즘을 함수로 만들면 되겠습니다.

제가 작성한 코드는 다음과 같습니다.

//동쪽으로 가는차는 P
//서쪽으로 가는차는 Q
//동쪽으로 간 차, 서쪽으로 간 차가 한쌍이상이면 +1
//총 지나친 차량의 수를 리턴

public int solution(int[] A) {
    	
   int count = 0;
   int maxSize = A.length;
   java.util.List<Integer> zero = new java.util.ArrayList<>();
    	
   for(int i=0; i<A.length; i++){
     if(A[i]==0){
    	zero.add(i);
    	}
    }

    int zSize = zero.size();
    for(int i = 0; i<zero.size(); i++){
    	if(count>1_000_000_000)return -1;
    	count+=maxSize-zero.get(i)+1-(zSize-i+1);
    }
    	
    if(count>1_000_000_000)return -1;
    	
       return count;
 }

제출을 하면 테스트가 진행되며 적당한 시간동안 인내하며 기다리면 됩니다^^

결과는 

다행히 100점이 나왔습니다 ㅎㅎ

이상 Codility 알고리즘관련 포스팅을 마치도록 하겠습니다.

Posted by Culinary developer