Two pointers, Sliding window

3-1, 3-2

ArrayList<Integer> answer = new ArrayList<>();
-> answer.add(xxx)

int[] a, int[] b
-> Arrays.sort(a), Arrays.sort(b)

ArrayList는 크기가 정해져있지 않기 때문에 add를 통해 추가 가능하다.
또한 배열은 Arrays.sort()를 통해 오름차순 정렬이 가능하다.

3-3

여러 일자가 있고 연속된 3일간의 최대 매출액을 구하는 문제이다.

public int solution(int n, int k, int[] arr) {
	int answer = 0, sum = 0;
    for (int i = 0; i < n-2; i++){
        for (int j = 0; j < k; j++) {
            sum += arr[j + i];
        }
        if (sum > answer) {
            answer = sum;
        }
        sum = 0;
    }
    return answer;
}

처음에 위와 같이 코드를 작성하였다. 이중 루프를 돌리다보니 Runtime Error가 발생하였다.
효율성을 O(n)으로 할 수 있는 문제는 최대한 O(n^2) -> O(n)으로 바꾸려 노력해보자.

public int solution(int n, int k, int[] arr) {
	int answer = 0, sum = 0;
    for (int i = 0; i < k; i++) sum += arr[i];
	answer = sum;
    for (int i=k; i<n; i++){
    	sum += (arr[i]-arr[i-k]);
        answer = Math.max(answer,sum);
    }   
	return answer;
}

위와 같이 바꾸게 되면 효율성이 좋아진다.

3-4

public int solution(int n, int m, int[] arr) {
	int answer = 0, sum = 0, lt=0;
    for (int rt = 0; rt < n; rt++) {
    	sum+=arr[rt];
        if(sum==m) answer++;
        while(sum>=m){
        	sum -= arr[lt++];
        	if(sum==m) answer++;
        }
    }
    return answer;
}

위의 것도 이중루프를 쓰지 않았다.
문제의 조건을 보면 1<N<100,000 이라 되어있는데, 이렇게 범위가 큰데 이중루프까지 쓰면 대략 10,000,000,000번의 연산이 필요해지는 것이다. 이런 것을 방지하고자 최대한 효율성을 좋게 만들어야할 것 같다.
if, while등은 여러번 반복해도 효율성이 크게 떨어지는 것 같지는 않다.

이러한 유형에서의 문제들은 lt, rt의 설정을 통해 효율적으로 코드를 구성하는 것이 가장 중요한 것 같다.
lt와 rt는 단순히 위치일 뿐이고 그 위치의 유동적인 변경을 통해 for문이 2번 혹은 그 이상 돌아가는 문제를 확연히 줄여낼 수 있다.
무작정 for문을 쓸 생각 말고 if 혹은 while문을 이용해 유동적으로 코드를 구상해보자