리스트에 순차적으로 접근해야 할 때 '두 점'의 위치를 기록하면서 처리하는 알고리즘
문제
첫 번째 줄에 첫 번째 배열의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 배열 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 배열의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 배열 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.
given
3
1 3 5
5
2 3 6 7 9일 때 [1 2 3 3 5 6 7 9]의 배열이 나와야 한다.
일반적으로 배열을 합친 후 sort를 진행하거나, sorting이 되어있는 컬렉션으로 진행 시 걸리던 O(n log n)의 시간 복잡도를
투 포인터 알고리즘을 이용함으로써 O(n)으로 줄일 수 있다.
풀이는 다음과 같다.
public class Main {
public ArrayList<Integer> solution(int n, int m, int[] arr, int[] arr2){
ArrayList<Integer> answer = new ArrayList<>();
int p1=0, p2=0;
while(p1<n && p2<m) {
if(arr[p1] < arr2[p2]) answer.add(arr[p1++]);
else answer.add(arr2[p2++]);
}
while(p1<n) answer.add(arr[p1++]);
while(p2<m) answer.add(arr2[p2++]);
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; i++) {
arr[i] = kb.nextInt();
}
int m = kb.nextInt();
int[] arr2 = new int[m];
for(int j=0; j<m; j++){
arr2[j] = kb.nextInt();
}
for(int x : T.solution(n, m, arr, arr2)) {
System.out.print(x + " ");
}
}
}
n배열과 m배열이 먼저 끝날때까지를 비교해놓고, 한쪽이 끝나면 나머지를 모두 추가하는 방식으로 구현한다.
'알고리즘 > 기타' 카테고리의 다른 글
| [JAVA]지뢰 찾기 - 델타 배열을 이용한 방법 (0) | 2023.02.02 |
|---|---|
| 소수 찾기 - 외부 메서드 없이 탐색 (0) | 2023.02.02 |
| 문자열 중복제거 - indexOf() (0) | 2023.01.29 |
| 문자열 전부뒤집기 - StringBuilder, toCharArray() (0) | 2023.01.27 |
