섹션 3. Two pointers, Sliding window[효율성 : O(n^2)-->O(n)] 1. 두 배열 합치기

문제

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

입력

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

출력

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

입출력 예제

---

풀이 방식을 정리해보자.

 

1. 2개의 배열이 필요하기 때문에 N과 M을 입력받고, 이를 통해 a[N] 과 b[M] 배열에 값을 입력받는다.

 

2. 메소드 구현으로 넘어가보자.

 

3. 배열로 리턴받을 것이기에 리턴형으로 메소드를 선언한다.

 

4. 두 배열의 포인터를 각각 p1, p2라고 선언하고 0으로 초기화한다.

• 포인터는 배열에서 각 값들이 있는 위치로 인덱스라고 생각하면 이해가 쉽다.

5. 두 배열 중 하나라도 배열의 마지막에 이르면 종료하도록 while 문을 작성한다.

• N은 a[ ] 배열의 최대개수이고 M은 b[ ] 배열의 최대개수이므로 전부 다 돌았으면 종료해야 한다.

6. if문을 통해 a[ ] 배열이 b[ ] 배열보다 값이 적으면 작은 값이 먼저 들어가야 하므로 p1 값을 배열에 넣는다.

• 이 때, ++ 의 위치를 조심해야 하는데 그 이유는 아래와 같다.
• p1++ : p1을 가리키는 값을 a[ ] 배열어 넣은 후, p1을 1 증가시킨다.
• ++p1 : p1을 증가시킨 후에, 증가한 값을 a[ ] 배열에 넣는다.

7. else 문을 통해 그 외의 조건에서는 b[ ] 배열에 있는 값을 넣는다.

• 즉, a[ ] 배열에 포인터가 가리킨 값이 b[ ] 배열보다 작으면, 먼저 결과 배열에 들어가야 하므로 값을 넣어준다.
• 그 후에 포인터의 위치를 1 증가시킨다.
• 해당 과정을 반복한다.

8. while 을 빠져나온 후에 a[ ] 배열 혹은 b[ ] 배열에 값이 남아있을 경우를 대비해서 코드를 추가 작성한다.

• 예를 들어 b[ ] 배열에 a[ ] 보다 큰 값이 여러개 있으면 나중에 b[ ] 배열에 값이 남게 되므로 이를 추가로 결과 배열에 넣어주어야 한다.

수행 결과를 확인한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.