BOJ 백준 11728: 배열 합치기

Table of contents

들어가며

이 문제는 $O(NlgN)$ 혹은 $O(N + M)$안에 정렬을 시킬 수 있는지 묻는 문제입니다.
저는 Two Pointers 기법으로 풀어서 $O(N + M)$ 시간 복잡도안에 해결했습니다.

풀이 과정

투 포인터로 각 배열의 포인터를 관리할 때, Out of Bound를 조심해서 코딩해야 합니다… ㅎ

AC 받은 Python 코드

import sys

input = sys.stdin.readline


def OOB(p, len_arr):
    if p < 0 or p >= len_arr:
        return True
    return False


if __name__ == "__main__":
    N, M = map(int, input().rstrip().split())
    A = [*map(int, input().rstrip().split())]
    B = [*map(int, input().rstrip().split())]
    lenA = len(A)
    lenB = len(B)
    ans = []
    # print(A)
    # print(B)
    aPointer = bPointer = 0
    while not OOB(aPointer, lenA) or not OOB(bPointer, lenB):
        if OOB(aPointer, lenA):
            ans.append(B[bPointer])
            bPointer += 1
            continue
        if OOB(bPointer, lenB):
            ans.append(A[aPointer])
            aPointer += 1
            continue

        if A[aPointer] <= B[bPointer]:
            ans.append(A[aPointer])
            aPointer += 1
        else:
            ans.append(B[bPointer])
            bPointer += 1
    print(" ".join(map(str, ans)))

번외: $O(NLgN)$ Tim Sort 이용하기

파이썬 기본 내장 정렬 라이브러리는 $O(NLgN)$를 보장합니다. 그래서 아래와 같이 짜도 AC를 받습니다.

import sys

input = sys.stdin.readline


if __name__ == "__main__":
    N, M = map(int, input().rstrip().split())
    ans = [*map(int, input().rstrip().split()), *map(int, input().rstrip().split())]
    ans.sort()
    print(" ".join(map(str, ans)))

참고로 Tim-Sort를 이용한다고 합니다. Tim-Sort Naver D2 블로그 아티클