한국사 요점정리 개발자

헐 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;

}

=<== 이건 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;
    }
}

A non-empty zero-indexed array A consisting of N integers and sorted in a non-decreasing order is given. The leader of this array is the value that occurs in more than half of the elements of A.

You are given an implementation of a function:

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

that, given a non-empty zero-indexed array A consisting of N integers, sorted in a non-decreasing order, returns the leader of array A. The function should return −1 if array A does not contain a leader.

For example, given array A consisting of ten elements such that:

  A[0] = 2 

  A[1] = 2

  A[2] = 2

  A[3] = 2

  A[4] = 2

  A[5] = 3

  A[6] = 4

  A[7] = 4

  A[8] = 4

  A[9] = 6

the function should return −1, because the value that occurs most frequently in the array, 2, occurs five times, and 5 is not more than half of 10.

Given array A consisting of five elements such that:

  A[0] = 1

  A[1] = 1

  A[2] = 1

  A[3] = 1

  A[4] = 50

the function should return 1.

Unfortunately, despite the fact that the function may return expected result for the example input, there is a bug in the implementation, which may produce incorrect results for other inputs. Find the bug and correct it. You should modify at most three lines of code.

Assume that:

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

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

array A is sorted in non-decreasing order.

Complexity:

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

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

Elements of input arrays can be modified.

위의 문제는 A라는 array에 값이 들어 있는데, 2,2,3,3,4,4 이런식으로 점점 커지는 수가 들어 있는 array이다. 이중 전체 갯수에서 같은수가 절반이 넘었을때 그때의 값을 리턴해 주고, 절반이거나 절반이 되지 않으면 -1을 리턴하라는 문제이다. 풀이보단 문제 이해가 너무 어려운 문제이다.

solution

public int solution(int A[]) {

int length = A.length;

// A 어레이의 길이가 0 이거나 1이면 -1을 리턴한다. 1개이면 절대 절반이상의 갯수를 만족할수 없다.

if (length <= 1) {

return -1;

}

// 첫번째 인자를 가장최근의 인자라고 생각할때

int lastInput = A[0];

int count = 0;

int tmpValue = -1;

for (int i = 0; i < A.length; i++) {

if(lastInput == A[i]) { // 가장 마지막에 가지고 있는 값과 첫번째 값이                     //같으면 카운트를 하나 올리고, 그 값을 저장하자

count++;

tmpValue = A[i];

// System.out.println("count : " + count);

}

else { // 만약 아니면 위에서 계산한 count를 계산하여 절반이상이면 

// return해주고, 아니면 count를 1로 세팅한다 (1로세팅하는 이유는 새로 하나가 추가됐기 

//때문이다

// System.out.println("count : " + count);

// System.out.println("(length/2) : " + (length/2));

if(count > (length/2)) {

return tmpValue;

}

else {

count = 1;

}

}

// 가장최근값을 가장 마지막에 저정한 값으로 넣어준다

lastInput = A[i];

System.out.println("lastInput : " + lastInput);

// 이건 마지막 놈을 체크하기 위한 루틴이다. 만약 이걸 하지 않으면 for문 //에서 else에서만 절반이 넘는지 체크를 하기 때문에 문제가 될수 있다. 예를들어 //{2,2,2,3,3,3,3,3} 이런식이면 if는 들어가지만 else에 못들어가 문제가 된다.

if(i == (length-1)) {

if(count > (length/2)) {

return tmpValue;

}

}

}

return -1;

}