[Python Algorithm] 탐색&시뮬레이션(string) - 두 리스트 합치기

> 탐색 & 시뮬레이션 (string 편)

 

📖 문제 : 두 리스트 합치기

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

 

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

 

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

 

입력예제 1

3
1 3 5
5

2 3 6 7 9

 

출력예제 1

1 2 3 3 5 6 7 9

 

import sys
# sys.stdin = open("input.txt", "r")
n = int(input())
a = list(map(int, input().split()))
m = list(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=' ')

 

⭐️ Point ! ⭐️

• 단순히 두개의 수 배열을 일일이 다 비교해가며 sort() 함수를 사용하여 하나의 리스트로 만들게 되면,
  주어진 배열의 데이터 수가 100000개 더 많을 수록 너무 느려지게 된다.
  
  이때 시간 복잡도는 O(nlogn)
  
  그래서 ! 여기서 선택한 방법은, 두 개의 배열이 이미 정렬되어있는 상태이므로
  만약, a[1,2,3,4,5,6], b[4,5,6,7,8] 라면 a와 b의 맨 앞부터 각각의 두개씩 원소를 비교해가면서 비교하여
  더 작은 수부터 다른 배열에 넣다 보면 나중에는 b[7,8]만 남게 되어 굳이 남은 배열의 수들은 비교할 필요 없이 남은 값 통째로 넣어주면 되는 것이다.
  
  이때의 시간 복잡도는 O(n) 
• a = list(map(int, input().split()))
  리스트 a에 '스페이스 바'로 구분된 값들을 나누어 원소로 넣어줌
  
  
• c = c + a[p1:]
  인덱스 p1값부터 끝까지 값을 다른 배열에 넣어줌

 

 

출처

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