[알고리즘 문제풀이] two pointers

(1-2) 공통원소 구하기

🚩 내 코드

 		Arrays.sort(a);
        Arrays.sort(b);

        int p1=0;
        int p2=0;
        ArrayList<Integer>al = new ArrayList<>();

        while (p1<n && p2<m){
            int i1 = Integer.parseInt(a[p1]);
            int i2 = Integer.parseInt(b[p2]);

            if(i1 > i2){
                p2++;
            }else if(i1 < i2){
                p1++;
            }else{
                al.add(i1);
                p1++;
                p2++;
            }
        }
        for(int i : al){
            System.out.print(i+" ");
        }

💡 푼 방식
두 배열을 오름차순으로 정렬
그리고 0인덱스부터 둘을 비교한다.
a배열 요소가 더 크다면 b배열 인덱스를 +1 (그래야 b가 커지므로)
b배열 요소가 더 크다면 a배열 인덱스를 +1
같다면 정답 배열에 추가 후 a,b배열 인덱스 모두 +1해준다.

📚 알게 된 정보
시간복잡도가 nlogn
그리고 공통원소를 찾는 과정을 O(n)

전체적으로는 시간복잡도는 O(nlogn)

(1-3) 최대매출

🚩 내 코드

 		 int N = Integer.parseInt(arr[0]);
        int K = Integer.parseInt(arr[1]);
        int [] days = new int[N];
        for(int i=0; i<N; i++){
            int money = scanner.nextInt();
            days[i] = money;
        }

        ArrayList<Integer> al = new ArrayList<>();
        int sum=0;
        int i=0;
        for(i=0; i<K; i++){
            sum+= days[i];
        }
        al.add(sum);
        for(int j=i; j<N; j++){
            sum-= days[j-K];
            sum+=days[j];
            al.add(sum);
        }
        Collections.sort(al);
        System.out.println(al.get(al.size()-1));

💡 푼 방식

먼저 k만큼의 요소를 더해서 arraylist에 넣는다.
그 뒤로 k만큼의 요소를 다시 계산해서 나아가는게 아니라
이미 계산한 값 sum에서 1번을 빼고 2번을 더해준다.

📚 알게 된 정보
기존값에서 변화량만 적용시켜주면
같은 행위를 반복하지 않아도 된다.

(1-4) 연속부분수열

🚩 내 코드

package two_pointers_sliding_window;
import java.util.Scanner;
public class 연속부분수열 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] arr = scanner.nextLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);
        int [] numbers = new int[n];

        for(int i=0; i<n; i++){
            numbers[i] = scanner.nextInt();
        }

        int sum = 0;
        int lt = 0;
        int ans = 0;

        for(int rt=0; rt<n; rt++){
            sum+=numbers[rt];
            if(sum == m){
                ans++;
            }
            while (sum >= m ){
                sum-=numbers[lt++];
                if(sum == m){
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

💡 푼 방식

for문으로 rt는 0부터해서 sum이 m이 될때까지 더한다.
만약 sum==m이면 answer++
그 후, while 문을 통해 lt가 가리키는 요소를 빼주고 lt는 한칸 오른쪽으로 가게 한다.
즉 rt는 for문으로 1씩 증가, 그 와중에 lt는 값을 비교하며 위치 변경

📚 알게 된 정보
two pointers알고리즘은
O(n^2)을 O(n)으로 바꿔주는 역할을 한다.
따라서 입력값이 엄청 클 때 사용하면 좋을듯..?!

(1-5) 연속된 자연수의 합

🚩 내 코드

 		Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());

        int lt = 0;
        int ans = 0;
        int sum = 0;
        int m = n/2+1;
        int[] arr = new int[m];

        for(int i=0; i<m; i++){
            arr[i] = i+1;
        }

        for(int rt=0; rt<m;  rt++){
            sum+=arr[rt];
            if(sum == n){
                ans++;
            }
            while(sum >= n){
                sum-=arr[lt++];
                if(sum == n){
                    ans++;
                }
            }
        }
        System.out.println(ans);

💡 푼 방식
배열로 각 숫자를 넣어주고, lt rt를 활용한 위의 방법과 같다.

📚 알게 된 정보
수학적으로 접근할 수도 있다.

   		Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        int ans = 0;
        int cnt = 1;
        n--; // 여기서 1 뺐고
        while(n>0){
            cnt++; //2돼서
            n=n-cnt; // 1과 2를 n에서 뺌.
            if(n%cnt == 0) ans++;
        }// cnt가 증가되고 빼지는 수도 계속 누적 됨.