인프런 3-1. 두 배열 합치기 (자바)

[문제]

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

[입력]

첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

[출력]

오름차순으로 정렬된 배열을 출력합니다.

[예시 입력 1]

3
1 3 5
5
2 3 6 7 9

[예시 출력 1]

1 2 3 3 5 6 7 9

---

[문제 풀이 과정]

음.. 이 문제는 상당히 여러가지 방식으로 풀 수 있을 것 같은데??
각각의 배열들은 왜 애초에 오름차순으로 주어질까??
일단 가장 처음 생각나는 방법으로는,
두 배열의 크기를 합친 크기의 배열 하나를 만들고
숫자 8개를 모두 받아들여서 일단 배열에 넣어놓은 다음에
그 8개를 그냥 오름차순으로 정렬하면 되지 않을까??
오름차순으로 정렬하는건 collection.sort함수가 있었던 것 같다!
이걸로 먼저 한번 풀어보자

1. N을 받아 들이고, arraylist 하나 만든다.
2.두번째 줄부터 나오는 숫자들을 리스트에 집어넣는다.
3. M은 받아.. 들여야 하나?
4. 네번째 줄부터 나오는 숫자들도 리스트 뒷부분에 집어넣는다.
5. collection.sort로 숫자를 오름차순 정렬한뒤 출력한다.

이 방법으로 했더니 쉽게 풀렸다!!

[처음으로 풀어서 통과한 코드]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		List<Integer> num = new ArrayList<>();
		
		for(int i = 0 ; i < N ; i++) {
			num.add(sc.nextInt());
		}
		
		int M = sc.nextInt();
		
		for(int i = 0 ; i < M ; i++) {
			num.add(sc.nextInt());
		}
		
		Collections.sort(num); // 오름차순 정렬
		
		for(int x : num) {
			System.out.print(x + " ");
		}
	}
}

collections.sort 안쓰고 그냥 푸는 방법은?
그럼 일단 배열을 한바퀴 돌면서 min값을 정한다.
min값을 제일 앞 값으로 해놓고 돌면서 더 작은거 있을때마다 덮어쓰기 하기
그래서 제일 작은 값 정해지면 제일 앞에 있는 값을 임시로 다른곳에 옮겨놓고
제일 앞 값에 걔를 넣은 다음에 마지막으로 덮어썼던 그 인덱스에
맨 앞에 있던 숫자 다시 넣어주기!!

[Collections.sort 함수 안 쓰고 풀어낸 코드]

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		
		List<Integer> num = new ArrayList<>();
		
		for(int i = 0 ; i < N ; i++) {
			num.add(sc.nextInt());
		}
		
		int M = sc.nextInt();
		
		for(int i = 0 ; i < M ; i++) {
			num.add(sc.nextInt());
		}
		
		// Collections.sort(num);
		// 함수 사용하지 않고 오름차순 정렬해보기!!
		
		int minNumIndex;
		int box;
		
		for(int i = 0 ; i < N+M ; i++) {
			minNumIndex = i;
			// 일단 제일 앞 값이 최솟값이라고 하기
			
			for(int j = i ; j < N+M ; j++) {
				if(num.get(j) < num.get(minNumIndex)) {
					minNumIndex = j;
					// 더 작은 숫자 나오면 걔로 대체
				}
			}
			
			box = num.get(i); // 제일 앞 값을 다른 곳으로 빼놓고
			num.set(i, num.get(minNumIndex)); // 제일 앞에 최솟값 집어넣기
			num.set(minNumIndex, box); // 최솟값 있던 곳에는 제일 앞값넣기
		}
		
		for(int x : num) {
			System.out.print(x + " ");
		}
	}
}

이 방법도 이제 익숙해져서 쉽게 할 수 있다!!

강의 듣기

그냥 합쳐서 정렬하라는 의도로 낸 문제가 아님!!!
퀵정렬 - 시간복잡도 O(nlogn)임. 960000번 돔
이거 말고 투포인터 이용해서 시각복잡도 O(n)으로 하라는 소리임!!
a 배열의 포인터는 p1, 얘는 1씩 인덱스를 0,1,2 이렇게 가리킬것임
b 배열의 포인터는 p2, 얘는 1씩 인덱스를 0,,2,,3,4 이렇게 가리킬것!!
그래서 a[p1]과 b[p2]를 비교해서 작은게 나올 때마다 answer배열에
하나씩 추가해주면됨. answer에 추가하고 나서 포인터를 하나씩 증가해주면 됨
a 배열에서 먼저 3개를 다 써버리면? 그럼 나머지 배열에서는
그냥 남은 숫자 전부 다 넣어버리면 되는것임
while 반복문 써주고 조건을 p1 < n && p2 < m 이렇게 잡아주면됨.
저건 둘중에 한 배열이 다 써지면 이제 반복문 끝내겠다는 뜻임.
근데 그럼 어느쪽이 먼저 쓰였는지 모르니까
밑에서도 while 반복문을 열어서 p1 < n 이면 a 배열 나머지 다 넣겠다.
또는 다른 while 반복문 열어서 p2 < m 이면 b 배열 나머지 다 넣겠다.
이렇게 해주면 됨!!

[투 포인터 사용해서 풀어낸 코드]

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] a = new int[N];
		
		for(int i = 0 ; i < N ; i++) {
			a[i] = sc.nextInt(); // a배열 따로
		}
		
		int M = sc.nextInt();
		int[] b = new int[M];
		
		for(int i = 0 ; i < M ; i++) {
			b[i] = sc.nextInt(); // b배열 따로
		}
		
		int p1 = 0, p2 = 0; // 포인터 두개 만들어주기
		// 포인터들은 각 배열의 인덱스를 가리킴.
		List<Integer> answer = new ArrayList<>(); // 정답리스트
		
		while(p1 < N && p2 < M) {
			if(a[p1] < b[p2]) {
				answer.add(a[p1]);
				p1++;
				// 위 두 줄은 answer.add(a[p1++])로 합칠수 있음.
				// p1++은 p1값을 넣은 다음 1증가 시키겠다는 소리임.
				// 후위연산임!!
			} else {
				answer.add(b[p2]);
				p2++;
			} // p1 == N이거나 p2 == M이면 둘중 한 배열을 다 쓴것!
		}

		while(p1 < N) {
			answer.add(a[p1++]); // 여기선 합쳐서 써봤음
			// 만약 a 배열이 아직 안 끝났으면 나머지 쭈루룩 다 넣기
		}
		while(p2 < M) {
			answer.add(b[p2++]);
			// 만약 b 배열이 아직 안 끝났으면 나머지 쭈루룩 다 넣기
		}
		
		for(int x : answer) {
			System.out.print(x + " ");
		}
	}
}

음.. 근데 세 방법 모두 시간이랑 메모리는 별 차이 안 남
어쨌든 투 포인터 이용해서 푸는 방법도 알게 됐당! 야호!!

[후기]

이번주 일요일에 코딩테스트 보니까 안 풀어본 유형들 빨리 풀어봐야겠당!!