4. 두 리스트 합치기

문제 설명

n번의 비교만으로 풀어낼 수 있는 방법이 있는 문제였다.(방법 까다롭다.)

sort 정렬 사용하면 8log8 이다.(nlogn)

---

*본 문제는 인프런 김태원 강사님의 파이썬 알고리즘 문제풀이 강의에 기반합니다.  

 

[문제 두 리스트 합치기 ]

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

 

-입력설명

첫번째 줄 세번째 줄에 각 리스트의 크기가 주어집니다. 

두 번째 줄, 네번째 줄에는 리스트 크기만틈의 원소가 오름차순으로 주어집니다.

 

-출력설명 

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

 

-입력예제1

3 

1 3 5

5

2 3 6 7 9

 

-출력예제1

1 2 3 3 5 6 7 9

 

 

풀이

두개의 리스트를 리스트로 받아서 더하기로 합쳐서 sort 로 호출하는 문제가 아니다.

sort로 함수를 호출하면  시간 복잡도가 8log8 이다. (nlogn)

그런데 이 문제는 이미 정렬되어 있는 것을 활용하면 n번만에 된다.  (8번만에)

 

비효율적인 코드

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()))

newList=a+b

newList.sort()
print(newList)

 

풀이

if a[p1]<b[p2] 이면 c.append()

else: c.append

 

#먼저 처리되고 남은 리스트 확인하고 남은 리스트는 c에 합친다.

#출력: 원소 하나씩 출력위해  for x in c: 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:]
    #p1부터 끝까지
if p2<m:
    c=c+b[p2:]
#print(c)
#원소 하나 출력위해
for x in c:
    print(x, end=' ')