[백준11728번] 배열 합치기

문제 링크 >> https://www.acmicpc.net/problem/11728

 

 

📋 문제

정렬되어있는 두 배열 A와 B가 주어진다.

두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

 

 

👉 입력

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다.

배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

 

 

👈출력

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

 

 

📝 풀이

import sys
n, m = map(int, sys.stdin.readline().split())
A = list(map(int,sys.stdin.readline().split()))
B = list(map(int,sys.stdin.readline().split()))
p1 = p2 = 0
arr = []

while p1 < n and p2 < m:
  if A[p1] <= B[p2]:
    arr.append(A[p1])
    p1 += 1
  else:
    arr.append(B[p2])
    p2 += 1

if p1 == n:
  for i in B[p2:]:
    arr.append(i)
else:
  for i in A[p1:]:
    arr.append(i)

print(*arr, sep=' ')

 

투포인터를 이용해서 풀었다.

A의 포인터가 될 p1, B의 포인터가 될 p2를 0으로 초기화하고 p1이 n과 같거나 p2가 m과 같아질 때까지 while문으로 순회한다.

A[p1]과 B[p2]를 비교하며 더 작은 것을 arr에 담고 해당하는 포인터의 값을 1 증가시킨다.

A와 B의 값이 같을 때에 대한 조건은 없어서 같은 경우에는 그냥 A의 것을 arr에 담도록 했다.

 

이후 while문의 순회가 끝나면 A와 B 중 길이가 더 긴 것의 요소들만 남게된다.

따라서 남은 것은 이미 정렬되어 있으니 그냥 arr에 더해준다.