파이썬 알고리즘 014 | 두 리스트 합치기**

14.두 리스트 합치기

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

▣ 입력설명
첫 번째 줄에 첫 번째 리스트의 크기 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

<내 풀이>

a=[]
for i in range(2):
    n=int(input())
    lst=list(map(int, input().split()))
    for i in lst :
        a.append(i)
        a.sort()
for i in a :
    print(i, end=' ')

=> 이런식으로 하면 강사님에 따르면 데이터가 더 많이 소진된다고 하셨다
앞으로도 계속 이렇게 리스트 안의 박스라고 생각하면서 접근해보려고 노력

근데 a랑 b중에 먼저 끝나버리는 자료 있을 것이다
그러면 break 걸어서 끝내
끝난 자료는 if로 알아보고, 둘중에 남은 자료의 남은 숫자들은
slice기능 사용해서 붙여버리면 된당

<풀이>

c=[]

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=' ')
    

<반성점>

• 리스트 안의 박스라고 생각하면서 접근해보려고 노력
• sort함수를 사용하게 되면 정렬하는데 걸리는 시간복잡도가 O(nlogn)인 반면, 이미 정렬되어 있다는 것을 이용한 풀이와 같은 방법은 O(n)이므로 이 중에서 더 효율적인 방법을 써야 한다

<배운 점>

• hashable
  사전은(set) hashable한 키만 받는다 - 키가 불변인 것만..키가 리스트처럼 변경 가능하면 나쁜 상황이 발생,
  tuple을 사용하면 된다!
  =>근데 사실 얘는 이번 문제에서 쓰일 일이 없었다