[백준 - Python] 11728. 배열 합치기

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

 

 

코드

첫 번째 풀이 : 유형을 생각하지 않은, 처음 떠올린 풀이

import heapq
from collections import deque

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

answer = []

while a:
    heapq.heappush(answer, a.popleft())
while b:
    heapq.heappush(answer, b.popleft())

for _ in range(len(answer)):
    print(heapq.heappop(answer), end=' ')

 

두 번째 풀이 : 포인터를 사용한 풀이

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

answer = []

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

if one < n:
    answer += a[one:]
if two < m:
    answer += b[two:]

print(*answer)

 

접근 방식

첫 번째 풀이

1. 투포인터 문제인 걸 알았음에도, 처음 떠올린 풀이로 진행

2. a, b 배열을 deque로 입력 받아 원소를 하나씩 꺼낼 때 시간을 단축하면 되겠다고 생각

3. 모든 원소를 heapq인 answer 변수에 삽입 → 자동 정렬

 

두 번째 풀이

1. a, b 배열이 정렬되어 있다는 점에서 포인터를 사용하면 더 시간이 단축 될 수 있겠다고 생각

2. a, b 배열의 첫 번째 원소에 포인터 초기화

3. 두 포인터가 가르키는 원소를 비교해서 작은 것부터 삽입

4. 포인터가 끝 원소까지 가지 못한 경우, 나머지 전부 삽입

 

배운 점

1. deque의 popleft() 연산은 O(1), 기본 리스트 `del` 연산은 O(n)

2. heappush(), heappop() 연산 시간 복잡도 O(logn) (n은 삽입/삭제 시 들어 있는 원소 수)

3. 시간 복잡도 분석 시, 가장 높은 시간 복잡도를 가지는 부분이 전체 코드의 시간 복잡도 결정

4. 첫 번째 코드의 시간 복잡도는 O(n logn)이기 때문에 통과

→ 입력이 1,000,000 (10^6, 백만) 이하인 경우, 최대 O(N logN)으로 끝내야 함 (1초 기준)

5. 두 번째 코드의 시간 복잡도는 O(n)이기 때문에 첫 번째 풀이보다 빠르다

6.

answer += a[one:]
answer += b[two:]

 

리스트 슬라이싱과 리스트 확장 연산자를 사용해,

원본 리스트를 변경하지 않고 새로운 리스트를 생성 및 추가할 수 있다