[탐색 및 시뮬레이션] 파이썬 알고리즘 문제 2-4 "두 리스트 합치기"

리스트 합치기

 

[시간복잡도]

O(nlogn)

: for 문 1개 + sort() 사용

[공간복잡도]

O(n) 

 

Problem

 

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

 

▣ 입력설명

 

첫 번째 줄에 첫 번째 리스트의 크기 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

 

💯 Solution ①

 

import sys
sys.stdin=open("input.txt","rt")
 
n1=int(input())
n1_list=list(map(int,input().split()))
 
n2=int(input())
n2_list=list(map(int,input().split()))
 
res=n1_list+n2_list
res.sort()
 
for i in res:
    print(i, end=" ")
 
 
 

- 간단하게 리스트를 합치고 하나씩 띄어쓰기하고 찍어낸다.

 

💯 Solution ②

: Tutor 님 Code

=> sort() 를 사용하면 편하지만, 사용하지 않고 코드를 작성해보자.

 

sort() 를 사용하면 시간복잡도가 O(nlog(n)) 이 되는데, 애초에 값이 정렬되어있기 때문에 sort()를 사용하는 것보다 사용하지 않고 코드를 작성하는 것이 시간복잡도가 더 좋다. 

 

sort() 를 사용한 경우 : O(nlogn)

sort() 를 사용하지 않은 경우 : O(n)

 

# sort()를 사용하지 않고 작성해보자
# 기존에 작성가능한 코드는 O(n) 인데 이를 O(nlogn)으로 바꿔보자
import sys
sys.stdin=open("input.txt","rt")
 
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
# p1이 n까지 못가고 남음
if p1<n:
    c=c+a[p1:]
if p2<m:
    c=c+b[p2:]
 
for x in c:
    print(x, end=" ")
 

 

- p1,p2 라는 값을 설정한다. 해당 값은 위치를 알려주는 포인터 역할이며, 초기값은 0이다.

- 합친 배열을 담을 c를 설정한다.

- while 문을 통해서, p1의 값이 n보다 작고 p2의 값이 m보다 작을 때 해당 조건문 코드가 동작한다.

- 만약, p1의 값이 n보다 크거나 p2의 값이 m보다 큰 경우가 발생한다면, 두 배열 중에서 하나의 배열을 다 돌았다는 것을 의미한다.

- 반복문의 조건을 성립한다면, 이제 a배열의 [p1] 값과 b배열의 [p2] 값을 비교해서 작은 값을 c에 가져다가 붙인다. (c.append(a[p1]) or c.append(b[p2]))

- 이럴 때, 다 돌지 않은 배열 (p1<n or p2<m)을 조건문으로 찾아서 다 돌지않은 배열의 나머지 리스트들을 c 뒤에 가져다가 붙이면 된다.

- 해당 출력양식에 맞춰서 for x in c: print(x, end=" ") 로 출력하면 된다.

 

📚 참고

[시간복잡도 계산]

 

wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

 

[파이썬 메서드별 시간복잡도]

www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt