[파이썬 알고리즘] 두 리스트 합치기

두 리스트 합치기

📄 문제

오름차순으로 정렬이 된 두 리스트가 주어지면
두 리스트를 오름차순으로 합쳐 출력하는 프로그램을 작성하세요.

▣ 입력설명
첫 번째 줄에 첫 번째 리스트의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 리스트 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 리스트의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 리스트 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.

▣ 출력설명
오름차순으로 정렬된 리스트를 출력합니다.

▣ 입력예제
3
1 3 5
5
2 3 6 7 9

▣ 출력예제
1 2 3 3 5 6 7 9

🧞 풀이

풀이

# 입력: N, N개의 리스트 원소, M, M개의 리스트 원소
# 출력: 오름차순으로 정렬된 리스트 출력

n = int(input())                            # 정수 n 할당
list_n = list(map(int, input().split()))    # 리스트 list_n 입력 및 할당
m = int(input())                            # 정수 m 할당
list_m = list(map(int, input().split()))    # 리스트 list_m 입력 및 할당

sum = [*list_n, *list_m]                    # 두 리스트 언패킹하여 다시 리스트로 묶어줌
sum = sorted(sum)                           # sorted()를 통해 오름차순 정렬
print(*sum, sep = ' ')                      # 언패킹하여 공백 하나 기준으로 값들 출력

 

다른 사람 풀이

# sort() 함수는 시간복잡도가 nlogn
# 이를 n으로 줄이는 방법

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

p1 = p2 = 0
c = []
while p1 < n and p2 < m:
    if a[p1] <= b[p2]:
        c.append(a[p1])
        p1 += 1
    else:
        c.append(b[p2])
        p2 += 1

if p1 < n:
    c = c + a[p1:]
if p2 < m:
    c = c + b[p2:]

for x in c:
    print(x, end = ' ')