두 리스트 합치기

오름차순으로 정렬이 된 두 리스트가 주어지면

두 리스트를 오름차순으로 합쳐 출력하는 프로그램 작성

 

입력으로 첫번째 리스트 크기받고 리스트1 원소들 주어지고

두번쨰 리스트 크기 받고 리스트2 원소들 주어짐

 

입력예시)

3

1 3 5

5

2 3 6 7 9

 

출력예시)

1 2 3 3 5 6 7 9

---

내가 쓴 코드1

#입력 전부 받기
N = int(input())
list1 = list(map(int, input().split()))
M = int(input())
list2 = list(map(int, input().split()))

# 두 리스트 합쳐서 오름차순 정렬
result = list1+list2
#sort()함수는 None을 리턴하기 때문에 변수에 sort()처리한 무언가를 "대입"할 경우 None이 반환된다는 점을 주의해야 함
result.sort()

# 결과 출력
print(result)

#이거는 너무 쉽고.. N과 M을 받은 이유가 없다.

 

내가 쓴 코드2

#첫번째 리스트를 먼저 받고 두번째 리스트의 요소들을 첫번째 리스트의 순서에 맞춰 사이사이에 끼워 넣는 식으로!


#입력받기
N = int(input())
lst1 = list(map(int, input().split()))
M = int(input())
lst2 = list(map(int, input().split()))

#두번째 리스트의 요소들을 첫번째 리스트를 탐색하며 크기에 맞춰 사이사이에 넣기
for x in lst2:
    for i in range(N):
        if x <= lst1[i]:
            #파이썬은 작거나 같다 표시가 되는구나
            lst1.insert(i, x)
            break
    else:
        lst1.append(x)
        #크.. for-else 구문 야무지게 썼당.

for x in lst1:
    print(x, end=' ')

 

내가 쓴 코드3

'''
sort() 사용 시 nlogn 시간복잡도
근데 이미 정렬된 리스트를 입력으로 받으니까!
n번만에 정렬이 가능하다!
모범답안의 방향성에 맞추어 다시 써보자!
'''

N = int(input())
lst1 = list(map(int, input().split()))
M = int(input())
lst2 = list(map(int, input().split()))
result = []

p1 = 0
p2 = 0

for _ in range(N+M):
    if lst1[p1] <= lst2[p2]:
        result.append(lst1[p1])
        p1 += 1
        if p1 == N:
            result = result + lst2[p2::]
            break
    else:
        result.append(lst2[p2])
        p2 += 1
        if p2 == M:
            result = result + lst1[p1::]
            break

for x in result:
    print(x, end = ' ')

 

모범답안

#모범답안
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 = ' ')

 

모범답안 보고 느낀점

 

접근방식을 생각할 때, 복잡도를 고려사항에 넣어야 하는데 .. 

배운거 다 까먹었는데 어떡해!

그래두 잘했다.ㅎ

---

다시써보기

N = int(input())
lst1 = list(map(int, input().split()))
M = int(input())
lst2 = list(map(int, input().split()))
result = []

p1 = p2 = 0

while p1 < N and p2 < M:
    if lst1[p1] <= lst2[p2]:
        result.append(lst1[p1])
        p1 += 1
    else:
        result.append(lst2[p2])
        p2 += 1

if p1 == N:
    result = result + lst2[p2:]
elif p2 == M:
    result = result + lst1[p1:]

for x in result:
    print(x, end = ' ')