[BOJ] 11728 배열합치기

https://www.acmicpc.net/problem/11728

정렬된 배열 두 개 합치는 문제이다. 예전에 프로젝트할 때 비슷한 상황이 있었는데 그때는 그냥 배열 두 개 연결하고 정렬했었는데, 더 나은 방법이 있는지 확인할 겸 풀어보았다.

투 포인터인 만큼 포인터 두 개 잡아서 각 배열의 첫 index부터 비교하면서 나갔다.
a배열의 값이 더 크면 b 배열의 값을 추가하고 index를 늘리고, 그 반대의 경우에는 a배열의 값을 추가하고 a의 index를 늘리는 방식으로 해결했다.

n, m = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

i = j = 0

answer = []

while i < n and j < m:
  if a[i] <= b[j]:
    answer.append(a[i])
    i+=1
  else:
    answer.append(b[j])
    j+=1

for x in range(i, n):
  answer.append(a[x])

for x in range(j, m):
  answer.append(b[x])

print(' '.join(map(str, answer)))

생각보다 시간이 오래 걸려서 배열에 매번 추가하는게 문제인가 싶어서 코드를 바꿨다.

n, m = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

i = j = 0

answer = [0] * (m+n)

while i < n and j < m:
  if a[i] <= b[j]:
    answer[i+j] = a[i]
    i+=1
  else:
    answer[i+j] = b[j]
    j+=1

for x in range(i, n):
  answer[x+j] = a[x]

for x in range(j, m):
  answer[i+x] = b[x]

print(' '.join(map(str, answer)))

0으로 채운 배열을 먼저 선언하고 i, j를 통해서 answer의 index를 추적하면서 업데이트 시켰다. 근데 이렇게 해도 시간이 비슷하게 나왔다.

혹시나 해서 예전에 사용했던 방법인 배열 두 개 합치고 정렬시키기를 해봤다.

n, m = map(int, input().split())

a = list(map(int, input().split()))
b = list(map(int, input().split()))

a = a+b
print(' '.join(map(str, sorted(a))))

이게 시간이 제일 빨리 나왔다. 메모리는 조금 더 잡아먹었지만 시간은 60%정도로 줄었다. 프로젝트할 때 마땅한 방법이 생각 안나서 지피티 선생님께 여쭤보니까 마지막 방법을 알려줬을 때 무식한 방법 같아서 의심스러웠는데 근거없는 추천이 아니었나보다.