Java 투포인터, 슬라이딩 윈도우 알고리즘 1

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

문제 1 :

오름차순으로 정렬된 두 배열이 주어지면 두 배열을 합쳐 오름차순으로 출력하는 프로그램을 작성하시오.

두 배열 n, m의 크기는 각각 1이상 100이하이다.

입력예제

3

2 5 9

4

3 5 6 7

출력예제

2 3 5 5 6 7 9

 

소스코드 :

import java.util.*;
class Main {
	public ArrayList<Integer> solution(int n, int[] arr1, int m, int[] arr2) {
		ArrayList<Integer> answer = new ArrayList<>();
		int p1 = 0, p2 = 0;
		while(p1<n && p2<m) {
			if(arr1[p1] < arr2[p2]) answer.add(arr1[p1++]);
			else answer.add(arr2[p2++]);
		}
		while(p1<n) {
			answer.add(arr1[p1++]);
		}
		while(p2<m) {
			answer.add(arr2[p2++]);
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr1 = new int[n];
		for(int i=0; i<n; i++) {
			arr1[i] = sc.nextInt();
		}
		int m = sc.nextInt();
		int[] arr2 = new int[m];
		for(int i=0; i<m; i++) {
			arr2[i] = sc.nextInt();
		}
		for(int x : T.solution(n, arr1, m, arr2)) {
			System.out.print(x + " ");
		}
	}
}

 

풀이 :

투포인터 알고리즘으로 문제를 해결한 것이다.

 

 

 

문제2 :

두 개의 집합이 주어지면 두 집합의 공통 원소를 추출해 오름차순으로 출력하시오

집합 n, m의 크기는 1이상 30000이하이다.

입력예제

5

5 2 1 6 7

5

2 4 6 5 8

출력예제

2 5 6

 

내 소스코드 [시간 복잡도 O(n²) ] :

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
class Main {
	public ArrayList<Integer> solution(int n, int[] arr1, int m, int[] arr2) {
		ArrayList<Integer> answer = new ArrayList<>();
		Arrays.sort(arr1);
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if (arr1[i] == arr2[j]) answer.add(arr1[i]);
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr1 = new int[n];
		for(int i=0; i<n; i++) {
			arr1[i] = sc.nextInt();
		}
		int m = sc.nextInt();
		int[] arr2 = new int[m];
		for(int i=0; i<m; i++) {
			arr2[i] = sc.nextInt();
		}
		for(int x : T.solution(n, arr1, m, arr2)) {
			System.out.print(x + " ");
		}
	}
}

풀이 :

arr1을 먼저 오름차순 정렬시키고 arr1을 기준으로 2중 for문을 돌려 공통 원소를 ArrayList에 저장하고 출력한다.

2중 for문을 사용하였으므로 시간복잡도는 O(n²)이다.

 

 

투포인터 알고리즘 이용한 소스코드 [시간 복잡도 O(n log₂ n) ] :

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Arrays;
class Main {
	public ArrayList<Integer> solution(int n, int[] arr1, int m, int[] arr2) {
		ArrayList<Integer> answer = new ArrayList<>();
		int p1 = 0, p2 = 0;
		Arrays.sort(arr1);
		Arrays.sort(arr2);
		while (p1<n && p2<m) {
			if (arr1[p1] == arr2[p2]) {
				answer.add(arr1[p1++]);
				p2++;
			}
			else if (arr1[p1] < arr2[p2]) p1++;
			else p2++;
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr1 = new int[n];
		for(int i=0; i<n; i++) {
			arr1[i] = sc.nextInt();
		}
		int m = sc.nextInt();
		int[] arr2 = new int[m];
		for(int i=0; i<m; i++) {
			arr2[i] = sc.nextInt();
		}
		for(int x : T.solution(n, arr1, m, arr2)) {
			System.out.print(x + " ");
		}
	}
}

 

알아둬야할건 Array.sort는 최악의 경우 시간복잡도가 O(n²)까지도 갈 수 있다는 것이다.

물론 해당 문제에선 O(n log₂ n)의 시간복잡도로 동작하지만 n의 범위가 큰 다른 문제에서는 쓰기 전에 생각해보도록 하자.