[백준] 2018 수들의 합 5 - 투 포인터 JAVA

https://www.acmicpc.net/problem/2018

2018번: 수들의 합 5

코드설명

투 포인터 문제입니다.

 

투 포인터를 구현하는 방법에는 다양한 방법이 있습니다.

첫번째 코드는, start를 for문으로 돌면서 체크하고,

두번째 코드는, while 문을 사용합니다.

 

투포인터 알고리즘의 시간복잡도는 O(N) 입니다. 이유는, 모든 N을 순회하며 원하는 값을 얻어내기에 그렇습니다.

코드

이중 포문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	twoPointer();
    }
    
    public static void twoPointer() {
    	int end = 1;
    	int intervalSum = 0;
    	
    	for(int start=1; start <= N; start ++) {
    		
    		while(intervalSum < N && end <= N) {
    			intervalSum += end;
    			end += 1;
    		}
            
    		if(intervalSum == N) {
//    			System.out.println(" "+start+" "+end);
    			answer += 1;
    		}
    		intervalSum -= start;
    	}
    	System.out.println(answer);
    }
    

}

 

 

while문

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N;
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	twoPointer();
    	System.out.println(answer);
    }
    
    public static void twoPointer() {
    	int start = 1;
    	int end = 1;
    	int intervalSum = 0;
    	
    	while(start <= N) {
    		
    		while(intervalSum < N && end <= N) {
    			intervalSum += end;
    			end += 1;
    		}
    		
    		if(intervalSum == N) {
    			answer += 1;
    		}
    		
    		intervalSum -= start;
    		start += 1;
    	}

    }
}