[2023-01-05]

Start

 

int size = A.length; 
int num = Integer.MAX_VALUE, num2 = 0; 
int pos = 0; 
Map<Integer, Integer> map = new HashMap<>(); 
for(int i = 0; i < size; i++) { 
	for(int j = i; j >= 0; j--) { 
		if (map.get(j) == null) { 
        	map.put(j, A[j]); 
        } else { 
            int temp = map.get(j) + A[i]; 
            map.put(j, temp); 
            if (num > (temp / (i - j + 1))) { 
                num = temp / (i - j + 1); 
                num2 = temp % (i - j + 1); 
                pos = j; } 
            else if (num == (temp / (i - j + 1)) && num2 > (temp % (i - j + 1)))
            { 
                num = temp / (i - j + 1); 
                num2 = temp % (i - j + 1); 
                pos = j; 
            }
      	} 
    } 
} 
return pos;

 

Triangle 문제

0 <= P < Q < R < N

A[P] + A[Q] < A[R]

A[Q] + A[R] < A[P]

A[R] + A[P] < A[Q]

을 만족하는 P, Q, R을 구하고 구할 수 있으면 1, 없으면 0을 리턴한다.

 

첫 시도는 조합으로 구해보았다.

성능 테스트에서 쉽지 않은 성적이 나와서.. 좀 다르게 생각해봐야할 거 같다.

추가한 부분은 for문이 돌 때 이미 답이 나왔을 때 더 이상 for문이 돌지 않도록 하는 것이다.

 

static int result, size;
    static int[] B, a;
    public int solution(int[] A) {
        result = 0;
        size = A.length;
        B = A;
        a = new int[3];
        combination(0, 0);
        // Implement your solution here
        return result;
    }

    public static void combination(int n1, int n2) {
        if (n2 == 3) {
            if(B[a[0]] + B[a[1]] > B[a[2]] 
            && B[a[1]] + B[a[2]] > B[a[0]] 
            && B[a[2]] + B[a[0]] > B[a[1]]) {
                result = 1;
            }
            return;
        }

        for(int i = n1; i < size; i++) {
            if(result == 1) {
                break;
            }
            a[n2] = i;
            combination(i + 1, n2+1);
        }
    }