BOJ 11728번 : 배열 합치기 (Python/Two-Pointer/Silver 5)

11728번: 배열 합치기

---

설명

정렬되어있는 두 배열 A, B를 합친 후 정렬해서 출력한다.
첫째 줄에는 배열 A, B의 크기 N과 M이 주어진다. (1부터)
둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다.

 

풀이

• 방법 1 - sort()

1. 문자형으로 입력받고 한 리스트에 A, B를 모두 저장한다.
2. 리스트 내에 있는 요소를 모두 정수형으로 변환한다.
3. sort()를 사용해 정렬하고 리스트에서 꺼내 출력한다.

• 방법 2 - two pointer algorithm

• 투 포인터 알고리즘은 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘을 의미한다

 

Solution

풀이 1. 정렬 사용

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
num = []
for _ in range(2):
    num += input().split() #['3', '5', '2', '9']
ans = []
for i in num:
    ans.append(int(i))
ans.sort() #문자형이라도 정렬이 된다. 그러나 사전순으로 정렬 됨 즉, 100과 11일 때 출력이 100 11임. 정답은 11 100
print(*ans)

 

풀이 2. 투 포인터 사용

import sys
input = sys.stdin.readline

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

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

left, right = 0, 0
ans = []
while left < n and right < m:
    if a[left] < b[right]:
        ans.append(a[left]) 
        left += 1
    else:
        ans.append(b[right])
        right += 1
#위의 while문에서 처리되지 못한 값을 처리하기 위함
while left < n:
    ans.append(a[left])
    left += 1
    
while right < m:
    ans.append(b[right])
    right += 1
    
print(' '.join(map(str, ans)))

 

TIL

• rsplit() : 오른쪽부터 문자열을 지정 구분자(기본값 : 공백) 기준으로 잘라서 리스트 생성

 

---

 

👩‍💻 회고

1차 제출에 실패했었는데 이유는, 정수형으로 변환시키지 않고 정렬을 시켰는데 잘 되길래 그대로 진행했다. 그러나 반례가 'A = 100, B = 11'일 때 답은 '11 100'인데 내 출력은 '100 11' 이었다. 정수라도 사전순으로 정렬되는 문제가 있어서 정수형으로 변환시키는 코드를 추가 시켰다.

 

2가지 풀이가 있는데 투 포인터로는 처음 풀어봐서 다른 풀이를 참고했다. 이분 탐색 알고리즘이랑 비슷해보여서 이해하기 쉬울 것 같다. 정렬과 투 포인터를 속도와 메모리 상에서 비교했을 때 투 포인터가 메모리를 더 많이 차지하지만, 속도는 조금 빠르다. 하지만 이 문제에서는 정렬을 쓰는 게 더 깔끔해 보이긴 한다. 

 

• 투 포인터 : 메모리 304392KB, 속도 1736 ms

• 정렬 :  메모리 295080, 속도 1760 ms