[알고리즘] Two pointers, Sliding window(1) : 두 배열 합치기(JAVA)

문제

풀이

🎨 쉬운 문제인데, 정렬로 문제를 풀면 시간복잡도가 커진다.

👕 main메소드

• n을 입력받고 입력받은 n만큼의 크기 배열 a를 만든다.
• m을 입력받고 입력받은 m만큼의 크기 배열 b를 만든다.
• for 문과 nextInt()를 이용해 입력값을 배열에 저장한다.
• 출력을 위한 코드

for(int x : T.solution(n,m,a,b)){
	System.out.print(x +" ");
}

T.solution에 매개변수 n,m,a,b 를 넣으면 반환되는 값을 x로 출력한다.

🩳 solution 메소드

• ArrayList< Integer> 를 반환한다. 매개변수는 main에서 입력받은 n,m(정수형)과 배열 a,b이다.

		ArrayList<Integer> answer = new ArrayList<>();

답을 저장할 ArrayList형식 정수형을 저장하는 변수 answer를 생성한다.

	int p1=0, p2=0;
		while(p1<n && p2<m){
			if(a[p1]<b[p2]) answer.add(a[p1++]);
			else answer.add(b[p2++]);
		}

• a의 포인터 p1, b의 포인터 p2를 0으로 설정 해준다.

• a는 0~n-1까지의 인덱스가 있으므로, p1<n 일 때 까지, b는 0 ~ m-1까지 인덱스가 있으므로 p2<m 이 동시에 참일때만 while문이 돌게 만들어 준다.

• a[p1]<b[p2] 가 참이면 p1을 add하고 ++해준다.

• 반대일 경우 p2를 add하고 ++해준다.

while(p1<n) answer.add(a[p1++]);
		while(p2<m) answer.add(b[p2++]);
		return answer;

나머지 부분을 출력해주면 끝!

소스코드

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

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