CountMultiplicativePairs

헐 27점. 시간도 중요한가 보다. 결과만 중요하다고 생각했는데...

Zero-indexed arrays A and B consisting of N non-negative integers are given. Together, they represent N real numbers, denoted as C[0], ..., C[N−1]. Elements of A represent the integer parts and the corresponding elements of B (divided by 1,000,000) represent the fractional parts of the elements of C. More formally, A[I] and B[I] represent C[I] = A[I] + B[I] / 1,000,000.

For example, consider the following arrays A and B:

  A[0] = 0 B[0] = 500,000

  A[1] = 1 B[1] = 500,000

  A[2] = 2 B[2] = 0

  A[3] = 2      B[3] = 0

  A[4] = 3 B[4] = 0

  A[5] = 5 B[5] = 20,000

They represent the following real numbers:

  C[0] = 0.5

  C[1] = 1.5

  C[2] = 2.0

  C[3] = 2.0

  C[4] = 3.0

  C[5] = 5.02

A pair of indices (P, Q) is multiplicative if 0 ≤ P < Q < N and C[P] * C[Q] ≥ C[P] + C[Q].

The above arrays yield the following multiplicative pairs:

(1, 4), because 1.5 * 3.0 = 4.5 ≥ 4.5 = 1.5 + 3.0,

(1, 5), because 1.5 * 5.02 = 7.53 ≥ 6.52 = 1.5 + 5.02,

(2, 3), because 2.0 * 2.0 = 4.0 ≥ 4.0 = 2.0 + 2.0,

(2, 4) and (3, 4), because 2.0 * 3.0 = 6.0 ≥ 5.0 = 2.0 + 3.0.

(2, 5) and (3, 5), because 2.0 * 5.02 = 10.04 ≥ 7.02 = 2.0 + 5.02.

(4, 5), because 3.0 * 5.02 = 15.06 ≥ 8.02 = 3.0 + 5.02.

Write a function:

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

that, given zero-indexed arrays A and B, each containing N non-negative integers, returns the number of multiplicative pairs of indices.

If the number of multiplicative pairs is greater than 1,000,000,000, the function should return 1,000,000,000.

For example, given:

  A[0] = 0 B[0] = 500,000

  A[1] = 1 B[1] = 500,000

  A[2] = 2 B[2] = 0

  A[3] = 2 B[3] = 0

  A[4] = 3 B[4] = 0

  A[5] = 5 B[5] = 20,000

the function should return 8, as explained above.

Assume that:

N is an integer within the range [0..100,000];

each element of array A is an integer within the range [0..1,000];

each element of array B is an integer within the range [0..999,999];

real numbers created from arrays are sorted in non-decreasing order.

Complexity:

expected worst-case time complexity is O(N);

expected worst-case space complexity is O(1), beyond input storage (not counting the storage required for input arguments).

Elements of input arrays can be modified.

public int solution(int A[], int B[]) {

double divider = 1000000d;

int aLength = A.length;

int bLength = B.length;

if(aLength != bLength) {

return -1;

}

if(aLength == 0 || bLength == 0) {

return -1;

}

double C[] = new double[aLength];

for (int i=0; i<aLength; i++) {

// System.out.println("C["+i+"] : " + (double)B[i] / 1000000);

C[i] = A[i] + (double)B[i] / divider;

System.out.println("C["+i+"] : " + C[i]);

}

return -1;

}

to be continue;

=> complete

public int solution(int A[], int B[]) {

double divider = 1000000d;

int aLength = A.length;

int bLength = B.length;

if(aLength != bLength) {

return -1;

}

if(aLength == 0 || bLength == 0) {

return -1;

}

double C[] = new double[aLength];

for (int i=0; i<aLength; i++) {

C[i] = A[i] + (double)B[i] / divider;

}

int count = 0;

int startIndex = -1;

do {

startIndex++;

for(int i=startIndex; i<C.length; i++) {

if(startIndex == i) {

continue;

}

double sum = C[startIndex] + C[i];

double multi = C[startIndex] * C[i];

if(multi >= sum) {

count++;

}

}

}

while(startIndex != C.length-1);

return count;

}

=<== 이건 55점짜리

몰랐던 사실인데, double 에 변수를 저장하면, 그대로 저장이 안되고 변경이 되는 수가 있다고 한다. 그래서 BigDecimal 변수를 사용해야 된다.

// you can also use imports, for example:
// import java.util.*;

// you can use System.out.println for debugging purposes, e.g.
// System.out.println("this is a debug message");
import java.math.*;

class Solution {
    public int solution(int[] A, int[] B) {
        int size = A.length;

		BigDecimal C[] = new BigDecimal[size];

		for (int i = 0; i < size; i++) {
			C[i] = BigDecimal.valueOf(A[i]).add(BigDecimal.valueOf((double) B[i] / 1000000d));
		}

		int count = 0;

		for (int i = 0; i < size; i++) {
			for (int j = i + 1; j < size; j++) {
				if (C[i].multiply(C[j]).compareTo(C[i].add(C[j])) >= 0) {
					count++;

					if (count > 1000_000_000) {
						return 1000_000_000;
					}
				}
			}
		}

		return count;
    }
}