[BOJ-11728] 배열 합치기 (Python)

🤒 문제

BOJ-11728 배열 합치기

💊 풀이

머지소트에서 머지 하는 과정으로 풀었다. 이유는 A, B는 정렬된 배열이라고 했기 때문에 A배열이나 B배열을 정렬 할 필요가 없기 때문이다.
두 배열에 대한 포인터 두개를 설정해서 두 수중 작은 수를 선택하고 포인터를 증가시키면 되는데,
비교가 끝난 뒤에 A 나 B 배열중 아직 비교하지 못한 수가 있을 수 있다. 남은 배열에 대한 코드도 추가해 줘야 한다.

result = []
n = 0
m = 0

while n <= N - 1 and m <= M - 1:
    if A[n] <= B[m]:
        result.append(A[n])
        n += 1
    else:
        result.append(B[m])
        m += 1

# A쪽이 남음
if m + 1 > M:
    result += A[n : N]

# B쪽이 남음
if n + 1 > N:
    result += B[m : M]

이런 식으로 했더니 시간이 2252ms 로 말도 안되게 느렸다.
최대한 함수 호출을 줄여보았다.
결과 배열을 길이가 N + M인 리스트로 만들고, index를 새로 하나 만들어서 index를 증가시키며 값을 대입했다.

result = [0 for _ in range(N + M)]
n = 0
m = 0
index = 0

while n <= N - 1 and m <= M - 1:
    if A[n] <= B[m]:
        result[index] = A[n]
        n += 1
    else:
        result[index] = B[m]
        m += 1
    index += 1

# A쪽이 남음
if m + 1 > M:
    for i in range(n, N):
        result[index] = A[i]
        index += 1

# B쪽이 남음
if n + 1 > N:
    for i in range(m, M):
        result[index] = B[i]
        index += 1

이렇게까지하면 1776ms 까지 줄일 수 있다.

여기서 마지막 출력하는 for문도 없애고, 리스트 만들고 대입하는 시간까지 없애기 위해서 새 배열을 만들지 않고 선택된 수를 바로 print 한게 완성된 소스코드 이다.

✨ 소스코드

N, M = map(int, input().split())
A: list = list(map(int, input().split()))
B: list = list(map(int, input().split()))

n = 0
m = 0

while n <= N - 1 and m <= M - 1:
    if A[n] < B[m]:
        print(A[n], end=" ")
        n += 1
    elif A[n] == B[m]:
        print(A[n], end=" ")
        print(B[m], end=" ")
        n += 1
        m += 1
    else:
        print(B[m], end=" ")
        m += 1

# A쪽이 남음
if m + 1 > M:
    for i in range(n, N):
        print(A[i], end=" ")

# B쪽이 남음
if n + 1 > N:
    for i in range(m, M):
         print(B[i], end=" ")