Two Pointers 알고리즘을 활용해서 풀었다.
Scanner 로 풀이하니 시간초과, BufferedReader 로 바꿔도 시간초과, BufferedWriter 까지 사용해서 겨우 통과했다 😵💫
각 배열마다 Pointer 를 하나 씩 부여하고 Pointer 가 가리키는 인데스를 비교하면서 값이 더 작은 것을 answer 리스트에 추가한다.
하나의 배열만큼 다 돌았으면, 비교할게 없으므로 나머지 배열을 전부 answer 에 다시 추가하면 끝 !
먼저 배열을 오름차순으로 정렬해서 풀어야 이렇게 풀어도 문제가 없다.
package backjoonsliver;
import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class BaekJoon11728 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] a = new int[n];
int[] b = new int[m];
StringTokenizer st1 = new StringTokenizer(br.readLine());
for (int i = 0; i < a.length; i++) {
a[i] = Integer.parseInt(st1.nextToken());
}
StringTokenizer st2 = new StringTokenizer(br.readLine());
for (int i = 0; i < b.length; i++) {
b[i] = Integer.parseInt(st2.nextToken());
}
List<Integer> answer = solution(a, b);
int size = answer.size();
for (int i = 0; i < size; i++) {
bw.write(String.valueOf(answer.get(i)));
bw.write(" ");
}
bw.flush();
bw.close();
}
private static List<Integer> solution(int[] a, int[] b) {
List<Integer> answer = new ArrayList<>();
Arrays.sort(a);
Arrays.sort(b);
int p1 = 0;
int p2 = 0;
while (p1 < a.length && p2 < b.length) {
if (a[p1] < b[p2]) {
answer.add(a[p1]);
p1++;
} else {
answer.add(b[p2]);
p2++;
}
}
while (p1 < a.length) {
answer.add(a[p1]);
p1++;
}
while (p2 < b.length) {
answer.add(b[p2]);
p2++;
}
return answer;
}
}
'알고리즘 정리' 카테고리의 다른 글
자바(Java) 알고리즘 문제풀이 학급 회장 [인프런 / Hash] (0) | 2022.04.18 |
---|---|
백준 12847번 꿀 아르바이트 (실버 4) (0) | 2022.04.16 |
백준 10757번[수학] 큰 수 A+B (0) | 2021.10.26 |
백준 2839번[수학] 설탕 배달 (0) | 2021.10.26 |
백준 2775번[수학] 부녀회장이 될테야 (0) | 2021.10.26 |