문제 / 두 리스트 합치기 / Python

 

문제 제목: 두 리스트 합치기

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

▣ 입력설명

 

첫 번째 줄에 첫 번째 리스트의 크기 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 = int(input())
a = list(map(int,input().split()))
m = int(input())
b = list(map(int,input().split()))
arr = []
for i in range(n):
    arr.append(a[i])
for i in range(m):
    arr.append(b[i])

arr = sorted(arr)
for i in arr:
    print(i,end = ' ')

.sort()함수는 자료복잡도가 O(nlogn)이다.

따라서 적은 양의 데이터를 처리 할 때는 상관 없겠지만, 방대해지면 자료복잡도가 O(n)인 구조를 쓰는게 좋다.

 

따라서 순서가 이미 정열되어있다면 그대로 입력하고, 순서가 틀린 경우에만 비교한 뒤 입력해주는 코드를 구현한다.

 

1. 두 지점을 가리키는 포인트 변수가 필요함
p1 -> a리스트의 0번 인덱스를 가리킴

p2 -> b리스트의 0번 인덱스를 가리킴

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

while문을 이용하여 포인트변수에 관한 조건문을 작성한다.

 

if p1<n:
    c=c+a[p1:]
if p2<m:
    c=c+b[p2:]
for x in c:
    print(x, end=' ')

포인트 변수의 비교가 끝난 변수는 그대로 모두 값이 출력되었겠지만, 나머지 포인트 변수를 가진 변수는 모두 출력이 안되었을 거다. 그러면 나머지부분만 슬라이싱을 하여 코드를 붙여서 넣어준다.

 

 

모범답안

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=' ')

---

※ 알아야 할 것

- sort()함수는 O(nlogn)의 자료복잡도를 가진다.