자바 알고리즘 문제 풀이 입문. 섹션3. Two Pointers, Sliding Window [효율성 : O(n^2) --> O(n)]

 

https://hyejin.tistory.com/1219

자바 알고리즘 문제 풀이 입문. 섹션2. Array(1, 2차원 배열) : 임시 반장 정하기

-> 이전 문제 풀이 

 

 

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

 

 

 

문제 풀이 1

public int[] solution(int[] a, int[] b)
{
   int[] answer = new int[a.length + b.length];
   
   System.arraycopy(a, 0, answer, 0, a.length);
   System.arraycopy(b, 0, answer, a.length, b.length);
   
   Arrays.sort(answer);
   
   return answer;
}

👩‍💻 : 나는 그냥 보자마자.. 음.. 합치고 정렬해야지 ~ 해서 arrayCopy 메서드와 sort를 사용해서 끝냈다..

(근데 강사님이 그러라고 문제 낸게 아니라고.. ㅋ ) 

 

간단하게 합치고, 정렬은 System.arraycopy 메서드와 Arrays.sort 메서드를 사용해서 풀 수도 있다..!

 

 

문제 풀이 2

public ArrayList<Integer> solution2(int n, int[] a, int m, 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;
}

👾 : 생각해보니 섹션 3의 주제는 Two Pointers 가 주제니까. .이를 사용했어야 한다ㅠ 

p1, p2 두개의 point를 만들고, p1은 a 배열을 돌고, p2는 b 배열을 돌면서 비교해주면 된다. 

while 반복문을 돌면서 p1이나 p2 둘 중 하나라도 배열을 모두 다 돌았으면 반복문을 나오고, 그 나머지 배열을 추가해주도록 했다. 

 

a[p1] < b[p1] 이면 먼저 answer에 a[p1]을 add 해주고, 그 다음 p1의 값을 +1 해주고, +1 해준  a[p1]과 b[p2]를 비교해주면 된다.