두 리스트 합치기

it 취업을 위한 알고리즘 문제 풀이

문제

코드

import sys
#sys.stdin = open("input.txt","rt")

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

list3 = list1 + list2

list3.sort()

for x in list3:
    print(x,end=" ")

import sys
sys.stdin = open("input.txt","rt")

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


i = 0
j = 0
while i < n1 and j < n2:
    if list1[i] < list2[j]:
        list3.append(list1[i])
        i += 1
    else:
        list3.append(list2[j])
        j += 1

#while i <n1:
#    list3.append(list1[i])
#    i +=1
#while j < n2:
#    list3.append(list2[j])
#    j+=1

#파이썬스러운 코드
if i < n1:
    list3 = list3 + list1[i:]

if j < n2:
    list3 = list3 + list2[j:]

for x in list3:
    print(x,end=" ")

문제해결방법

• 첫 번째는 파이썬스러운 코드로 구현해보았다.
  • 두 리스트를 받은 후 +연산자로 리스트를 합쳐서 새로운 리스트에 저장하고 정렬한 후 출력했다.
  • 이 방법은 sort 함수가 NlogN의 시간 복잡도를 가지므로 더 좋은 방법을 생각했다. 문제에서 주어지는 리스트의 값들이 이미 정렬된 형태이기 때문에 2개의 포인터 변수를 활용해서 비교하면 N의 시간복잡도를 가진 코드를 작성할 수 있다.
• 두 번째 방법은 포인터 변수를 두어 리스트의 요소들을 비교하며 정렬하는 방법으로 구현했다.
  • i,j 포인터 변수가 모두 list1과 list2의 크기보다 작을 때 두 포인터 변수는 리스트의 요소들을 가리키고 list1[i]와 list2[j]의 값을 비교하여 작은 값을 list3에 넣어 주었다.
  • 반복문이 종료된 후에는 한 리스트의 값들이 남았다는 것이고 이 리스트는 다른 리스트의 값들보다 모두 크기 때문에 list3 뒷부분에 합쳐 주기만 하면 된다. 합칠 때는 슬라이싱기능을 이용해서 합쳐주었다.