[인프런 - 파이썬 알고리즘 문제풀이] 3.4 두 리스트 합치기

인프런 > 파이썬 알고리즘 문제풀이

섹션 3.4 두 리스트 합치기

👊 내 문제 풀이

+ 혹은 __add__ 메서드를 이용해 두 리스트를 결합한 후 오름차순으로 정렬한다.

n1 = int(input())
list1 = list(map(int, input().split()))
n2 = int(input())
list2 = list(map(int, input().split()))

# list1 + list2 후 정렬
list1 = sorted(list1+list2)
for i in list1:
    print(i,end=" ")

채점 결과

 

💡 강의 해답

이 문제는 이미 정렬되어 입력되기 때문에, 이를 활용하는 것(O(n))이 sort() 내장함수를 쓰는 것(O(nlogn))보다 시간복잡도가 좋다.

n=int(input())
a=list(map(int, input().split()))
m=int(input())
b=list(map(int, input().split()))
p1=p2=0
c=[]
#p1이 n에 도달하거나 p2가 m에 도달할 때까지
while p1<n and p2<m:
    if a[p1]<b[p2]:
        c.append(a[p1])
        p1+=1
    else:
        c.append(b[p2])
        p2+=1
#p2가 m에 도달하면 p1의 나머지 인덱스 연결
if p1<n:
    c=c+a[p1:]
#p1이 n에 도달하면 p2의 나머지 인덱스 연결
if p2<m:
    c=c+b[p2:]
for x in c:
    print(x, end=' ')

리스트 더하기