[ 백준 ] 11728번 - 배열 합치기 (Python)

기본 정보

• Level: silver 5
• Problem Link: 배열 합치기
• Problem Number: 11728
• My Solution Link: 나의 풀이
• Algorithm I used: 투포인터(two pointer)

문제

• 정렬된 두 배열을 합친 다음 이를 정렬해보자.

알고리즘

• 입력으로 주어진 크기만큼 반복해서 각 배열 값 받기
• 투 포인터 방식
  • 각 배열에 포인터를 두고 그 둘이 가리키는 수 중 더 작은 순서대로 결과 배열에 집어넣으며 포인터를 이동시킨다.
• 그냥 list에서 이중 for문을 도니까 outer loop 파트에서 진전시킬 때 구현하기 힘들다.
  • list를 queue/stack으로 변경해야 하는가?
  • pop시키는 두 가지 방법
    • 각 리스트 역순 정렬 후 pop
    • 리스트를 deque로 변경한 후 popleft 진행

나의 시도

_,_ = map(int,input().split())

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

a.sort(reverse=True)  # O(NlogN)
b.sort(reverse=True)

result = []

# 각 리스트가 비었는지 여부 체크
while a and b:
    if a[-1] > b[-1]:
        result.append(b.pop())  # 둘 다 O(1)
    elif a[-1] < b[-1]:
        result.append(a.pop())  # 둘 다 O(1)
    else:
        result.extend((a.pop(),b.pop()))  # O(N)

## 둘 중 하나 이상이 빈 상태
# a가 빈 상태
if not a:
    result.extend(sorted(b))  # O(NlogN)

# b가 빈 상태
if not b:
    result.extend(sorted(a))

print(*result)