Codility # 11. Equileader

오...꽤 어려운 문제 만났다.
맨처음에 문제를 그리 안 오래 걸리고 풀었는데, 정답은 맞췄으나 시간복잡도에서 터져버렸다. 그 이유는, 중복되는 계산을 N번 만큼 계속해서 해줬기 때문이다.

그래서 어떻게 시간절약도를 줄일 수 있을까 고민하다가, 중복되는 계산을 기억할 수 있게 해주었다.
물론 이것을 하려면 조금 더 생각할 줄 알아야 한다.

그리고 인덱스 관리할때, 처음에 확실하게 잡고 넘어가자.
이 문제는 실수를 너무많이해서 시간이 오래 끌렸다.
실수 리스트
1) 부분 배열의 크기 구하는 방법
-> 해결 방법 : 첫번째, 2번째 확실하게 예시 잡고 하기
2) 시간 복잡도 N^2은 오바
-> 해결 방법 : 재사용 로직 확실하게 잡기 코드 짜기 전부터

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

// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
	public static int find(int[] b) { // 과반 인지 아닌지, 과반 일 경우숫자 배
		int maxNum = Integer.MIN_VALUE;
		int maxCount = 0;
		int count = 1;
		boolean tie = false;
		for(int i = 0; i < b.length; i++) {
			if(i < b.length-1 && b[i] == b[i+1]) {
				count++;
			}else {
				if(count > maxCount) {
					maxCount = count;
					count = 1;
					tie = false;
					maxNum = b[i];
				}else if(count == maxCount) {
					tie = true;
				}
			}
		}
		if(tie) {
			maxNum = Integer.MIN_VALUE;
		}
		return maxNum;
	}    

    public int solution(int[] A) {
		int N = A.length;
		int[] newA = A.clone();
		Arrays.sort(newA);
		int leader = find(newA);
		int howMany = 0;
		int[] B = new int[N];
		int ccount = 0;
		for(int i = 0; i < N; i++) {
			if(A[i] == leader) {
				ccount++;
			}
			B[i] = ccount;
		}
		int front,back = 0;
		boolean frontrs, backrs = false;
		for(int i = 0; i < N-1; i++) {
			frontrs = false;
			backrs = false;
			front = B[i];
			back = B[N-1] - front;
			if(front > (i+1)/2) {
				frontrs = true;
			}
			if(back > (N - (i + 1))/2) {
				backrs = true;
			}
			if(frontrs && backrs ) {
				howMany++;
			}
			
		}
		return howMany;

    }
}