탐색&시뮬레이션 문제 #4. 두 리스트 합치기

*이 풀이는 인프런: 파이썬 알고리즘 문제풀이 강좌에 기반하였습니다.

 

 

 

내 풀이

 

1. 파이썬은 '+' 덧셈 연산으로 리스트를 합칠 수 있다는 점을 이용한다.

 

import sys
#sys.stdin=open("input.txt","rt")
res=[]
for i in range(2):
    n=int(input())
    arr=list(map(int,input().split()))
    res+=arr
res.sort()
for x in res:
    print(x, end=' ')

 

 

 

강사님 풀이

 

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

if p1<n:
    c=c+a[p1:]
if p2<m:
    c=c+b[p2:]
    
for x in c:
    print(x, end=' ')

 

 

 

배운 점

 

1. 파이썬의 sort( )함수는 퀵정렬로 평균 O(NlogN)이 걸린다.

하지만 이미 정렬되어 있는 값이 주어진 경우라면, 이를 이용해서 O(N)이 걸리도록 만들어 줄 수 있다.

 

두 리스트에 포인터를 두고, 각 리스트의 값을 대소비교하면서 정렬한다.

 

 

2. a[ x ]는 배열에 있는 값을 가르키지만, a[ x : ]는 x부터 끝까지 배열을 가르킨다.

ex) a = [ 1 , 3 , 5 ]  ->  a[ 0 ] = 1, a[ 0: ] = [ 1, 3, 5 ]