파이썬 예제코드) 정수 리스트 2개를 병합하기 (+Merge algorithm)

#1. 문제 해결

 1) 원소 개수가 다른 두개의 정수 리스트 만들기 (오름차순으로 정렬)

 2) len으로 각 리스트의 원소개수를 M, N변수에 넣기

 3) 두 리스트의 원소개수의 합만큼 원소가 생기도록 (M+N) 병합된 리스트에 0을 넣기

 4) 각 리스트의 인덱스는 모두 0으로 넣어서 시작

 5) while문으로 첫번째 리스트와 두번째 리스트의 인덱스 중 하나라도 마지막 인덱스까지 달할 때까지

     반복해서 병합 리스트에 원소를 넣음 (병합 리스트에는 둘 중 원소값이 작은 것을 넣음)

 6) 세개의 리스트의 인덱스 값을 상황에 맞게 1씩 증가시키기

 7) 첫번째 리스트의 인덱스와 두번째 리스트의 인덱스 중 아직 끝까지 도달하지 않은 리스트의 경우 그 뒤로 병합 리스트에 들어가도록 함

 8) 마지막에 병합된 리스트 확인

 

#2. 코드 짜기

# 병합 알고리즘 만들기 (Merge)
## 2개의 정수 리스트 합치기
list1=[1,3,5]
list2=[2,4,6,8]
M=len(list1); N=len(list2)
m_list=[0]*(M+N) #병합된 리스트; 병합 리스트의 원소 개수=list1 원소 개수 + list2 원소 개수
i=0; j=0; k=0
while i<M and j<N: #둘 중 하나라도 끝에 도달할 때까지
  if list1[i]<list2[j]:
    m_list[k]=list1[i]
    k+=1; i+=1
  else:
    m_list[k]=list2[j]
    k+=1; j+=1
while i<M:
  m_list[k]=list1[i]
  k+=1; i+=1
while j<N:
  m_list[k]=list2[j]
  k+=1; j+=1
print(m_list)

 

#3. 실행