효율성[O(n2) -> O(n)] 섹션 - (2)

효율성[O(n2) -> O(n)] 섹션 - (2)

3-5-(1). 연속된 자연수의 합 (two pointers)

• 연속된 자연수의 합으로 정수 N을 표현할 때는~ N/2 + 1 까지의 범위 내에서만 확인하면 된다.

import java.util.Scanner;

/* 3-5. 연속된 자연수의 합 
[설명]
N입력으로 양의 정수 N이 입력되면 
2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요.
*/
public class Main1 {
    //솔루션 함수 
    public int solution (int N) {
        int answer = 0, sum = 0, lt= 0;
        int m = N/2+1;
        int[] arr = new int[m];
        for(int i = 0; i<m; i++) {
            arr[i] = i+1;
        }

        //two pointers 알고리즘 적용한 실질 로직 
        for(int rt = 0; rt<m; rt++) {
            //1씩 증가하는 rt 따라 sum 누적하면서
            sum += arr[rt];
            if(sum == N) {
                answer++;
            }
            //근데 sum >= n 이 되면 (같을 때도 빼줘야 함 다음 꺼 찾게)
            while(sum >= N) {
                sum -= arr[lt++];
                if(sum == N) answer++;
            }
        }
        return answer;
    }
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T  = new Main1();

        Scanner kb = new Scanner(System.in);
        int N = kb.nextInt();

        System.out.println(T.solution(N));        
    }
}

3-5-(2). 연속된 자연수의 합 (수학)

import java.util.Scanner;

/* 3-5. 연속된 자연수의 합 (수학적인 방식으로 접근)
*/
public class Main2 {
    //솔루션 함수 
    public int solution(int n ) {
        int answer = 0, cnt = 1;
        n--; //1 뺐고
        while(n > 0) {
            cnt++; 
            n = n- cnt; //2 뺐고, 3뺐고 ... 답 나올 때까지 뺌
            if(n % cnt == 0) { //답이 나오면 
                answer++;
            }
        }
        return answer;
    }    
    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Main2 T = new Main2();
        Scanner kb = new Scanner(System.in);

        int n = kb.nextInt();
        System.out.println(T.solution(n));
    }
}

3-6. 최대 길이 연속 부분 수열 (Two Pointers 알고리즘) * 어려움 ㅠ**

/* 3-6. 최대 길이 연속 부분 순열 ** 어려움 ㅠㅠ
[입력]
첫 번째 줄에 수열의 길이인 자연수 N(5<=N<100,000), k가 주어집니다.
두 번째 줄에 N길이의 0과 1로 구성된 수열이 주어집니다.
[출력]
첫 줄에 최대 길이를 출력하세요.
*/
public class Main1 {
    //솔루션 함수
    public int solution(int n, int k, int[] arr) {
        int answer = 0, cnt = 0, lt=0;

        for(int rt = 0; rt<n; rt++) {
            if(arr[rt] == 0) cnt++;
            while(cnt>k) {
                if(arr[lt] == 0) cnt--;
                lt++;
            }
            answer = Math.max(answer, rt-lt+1);//최대 길이로 갱신 
        }

        return answer;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];

        for(int i = 0; i<n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, k, arr));
    }
}