[알고리즘_코딩 테스트_JAVA] 투 포인터 (JAVA, PYTHON)

본문은 알고리즘 코딩테스트 자바편을 정리한 내용입니다 :)

 

✔ 문제 006 숫자의 합 구하기

 

⬜ 투 포인터 이동원칙

start_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수에서 왼쪽 값을 삭제하는 것과 효과가 같다.

end_index를 오른쪽으로 한 칸 이동하는 것은 연속된 자연수의 범위를 한 칸 더 확장하는 의미이다.

같을 때는 경우의 수를 1 증가시키고, end_index를 오른쪽으로 이동시킨다.

• sum > N : sum  = sum - start_index; start_index++;
• sum < N : end_index++; sum = sum + end_index;
• sum == N : end+index++; sum = sum + end_index; count++;

문제 바로가기 💨 

이 문제의 시간 제한은 2초이다. 그런데 N의 최대값은 10,000,000으로 매우 크게 잡혀있다. O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 한다. 이런 경우 자주 사용하는 방법이 투 포인터이다.

 

JAVA

import java.util.*;

class Main {
	public static void main (String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int N = sc.nextInt();
	    int count = 1; // 자기자신 하나로 이루어진 경우 수 미리 저장
	    int start_index = 1;
	    int end_index = 1;
	    int sum = 1;
	    
	    while(end_index != N) {
	        if(sum == N) { // 현재 연속 합이 N과 같은 경우
	            count ++;
	            end_index++;
	            sum = sum + end_index;
	        }else if(sum > N) { // 현재 연속 합이 N보다 더 큰 경우
	            sum = sum - start_index;
	            start_index++;
	        } else{ //현재 연속 합이 N보다 작은 경우
	            end_index++;
	            sum = sum + end_index;
	        }
	    }
	    System.out.println(count);
	}
}

Python

n = int(input())
count,start_index,end_index,sum = 1,1,1,1
while end_index!=n:
    if sum == n:
        count+=1
        end_index+=1
        sum = sum + end_index
    elif sum > n:
        sum = sum - start_index
        start_index+=1
    elif sum < n:
        end_index+=1
        sum = sum + end_index

print(count)

 

✔ 문제 007 주몽의 명령

문제 바로가기 💨 

⬜ 투 포인터 이동원칙

A[i] + A[j] > M : j--; // 번호 합이 M보다 크므로 큰 번호 index를 내린다.
A[i] + A[j] < M : i++; // 번호 합이 M보다 작으므로 작은 번호 index를 올린다.
A[i] + A[j] == M : i++; j--; count++; // 양쪽 포인터를 모두 이동시키고 count를 증가

이 문제는 두 재료의 번호 합, 즉 크기를 비교하므로 값을 정렬하면 문제를 좀 더 쉽게 풀 수 있다. N의 최대 범위가 15,000이므로 O(nlogn) 시간 복잡도 알고리즘을 사용해도 문제가 없다. (일반적으로 정렬의 시간 복잡도는 O(nlogn) )

O(nlogn)

알고리즘 로직

JAVA

import java.util.*;
import java.io.*;

class Main {
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int N = Integer.parseInt(br.readLine()); // 재료 개수
	    int M = Integer.parseInt(br.readLine()); // 갑옷이 완성되는 번호의 합
	    int[] A = new int[N];
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    for(int i = 0; i < N; i++) { // 재료 입력 받기
	        A[i] = Integer.parseInt(st.nextToken());
	    }
	    // 재료 배열 정렬하기
	    Arrays.sort(A);
	    int count = 0;
	    int i = 0;
	    int j = N -1;
	    while(i<j) {
	        if(A[i] + A[j] < M) {
	            i++;
	        } else if (A[i] + A[j] > M) {
	            j--;
	        } else{
	            count++;
	            i++;
	            j--;
	        }
	    }
	    System.out.println(count);
	    br.close();
	}
}

Python

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
li = list(map(int,input().split()))

li.sort()
count,i,j = 0, 0, n-1

while i<j:
    if li[i] + li[j] < m:
        i+=1
    elif li[i] + li[j] > m:
        j-=1
    else:
        count+=1
        i+=1
        j-=1

print(count)

 

✔ 문제 008 '좋은 수' 구하기

문제 바로가기 💨 

좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N제곱보다 작아야 한다. 만약 시간 복잡도가 N제곱인 알고리즘을 사용하면 최종 시간 복잡도는 N 세제곱이 되어 제한 시간 안에 문제를 풀 수 없다. 따라서 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(nlogn) 이어야 한다. 두 수의 합, 시간 복잡도를 고려할때 투 포인터 알고리즘을 사용하면 된다.

다만 정렬된 데이터에서 자기 자신을 좋은 수 만들기에 포함하면 안된다. 이 점을 예외로 처리해야 한다. (ex_ 0 3 3 => 좋은 수 X!)

 ⬜ 투 포인터 이동원칙

• A[i] + A[j] > K : j--; A[i] + A[j] < k : i++;
• A[i] + A[j] == K : i++; j--; count++;

배열의 모든 수에 대하여 투포인터 알고리즘 반복

JAVA

import java.util.*;
import java.io.*;

class Main {
	public static void main (String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int N = Integer.parseInt(br.readLine()); // 수의 개수
	    int res = 0;
	    long A[] = new long[N];
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    for(int i = 0; i < N; i++){ // 수 입력받기
	        A[i] = Long.parseLong(st.nextToken());
	    }
	    Arrays.sort(A); //정렬
	    
	    // 배열안의 각 숫자에 대해서 투포인터 알고리즘 수행
	    for(int k = 0; k < N; k++){
	        long find = A[k];
	        int i = 0;
	        int j = N-1;
	        // 투 포인터 알고리즘
	        while(i < j) {
	            if(A[i] + A[j] == find){
	                //find 는 서로 다른 두 수의 합이어야 한다.
	                if(i != k && j != k){
	                    res++;
	                    break;
	                } else if(i==k) {
	                    i++;
	            } else if(j==k){
	                j--;
	            }
	            } else if(A[i] + A[j] < find){
	                i++;
	            } else{
	                j--;
	            }
	        }
	    }
	    System.out.println(res);
	    br.close();
	}
}

Python

import sys
input = sys.stdin.readline

n = int(input())
li = list(map(int,input().split()))
li.sort()

count=0
for k in range(0,n):
    find = li[k]
    i, j = 0, n-1
    while i < j:
        if li[i] + li[j] == find:
            if i!= k and j!=k:
                count+=1
                break
            elif i==k:
                i+=1
            elif j==k:
                j-=1
        elif li[i] + li[j] < find:
            i+=1
        else:
            j-=1

print(count)