[문제]
오름차순으로 정렬이 된 두 리스트가 주어지면 두 리스트를 오름차순으로 합쳐 출력하는 프로 그램을 작성하세요.
▣ 입력설명
첫 번째 줄에 첫 번째 리스트의 크기 N(1<=N<=100)이 주어집니다.
두 번째 줄에 N개의 리스트 원소가 오름차순으로 주어집니다.
세 번째 줄에 두 번째 리스트의 크기 M(1<=M<=100)이 주어집니다.
네 번째 줄에 M개의 리스트 원소가 오름차순으로 주어집니다.
각 리스트의 원소는 int형 변수의 크기를 넘지 않습니다.
▣ 출력설명
오름차순으로 정렬된 리스트를 출력합니다.
▣ 입력예제
3
1 3 5
5
2 3 6 7 9
▣ 출력예제
1 1 2 3 3 5 6 7 9
[풀이]
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: # 두 개의 리스트 중 하나라도 끝까지 같다면 이 while 문은 끝
if a[p1] <= b[p2]:
c.append(a[p1])
p1 += 1
else:
c.append(b[p2])
p2 += 1
# 남은 자료가 무엇인지 확인
if p1<n: # p1이 n까지 가지 못하고 남았을 경우
c = c+a[p1:]
if p2<m:
c = c+b[p2:]
for x in c:
print(x, end=' ')
[내용]
1. sort 시간복잡도: nlogn
처음에 sort() 함수를 이용해서 풀었더니 시간초과가 나왔다. sort 함수의 시간복잡도가 nlogn 이여서 그랬던 것 같다.
이 문제에서는 이미 정렬되어 있는 리스트 이므로 시간복잡도가 n 이 되게 해야 한다. 각 리스트를 가리키는 포인터 p1, p2 를 이용해서 문제를 풀어야 했었다.
<알고리즘 설명>

1. 두 리스트의 인덱스를 가리키는 p1, p2 사용. 각각의 위치에 있는 값들을 비교해서 둘 중 작은 값을 정답인 c에 대입한다. 이후엔 둘 중 작은 값이 있는 곳의 인덱스를 1씩 추가 시킨다.

마지막이 되었을때는 리스트의 남은 부분들을 정답인 c에 그대로 넣는다.
'Coding Test > Python' 카테고리의 다른 글
| [Python] 격자판 최대합 (0) | 2023.01.31 |
|---|---|
| [Python] 수들의 합 (0) | 2023.01.30 |
| [Python] 카드 역배치 (0) | 2023.01.29 |
| [Python] 숫자만 추출 (0) | 2023.01.25 |
| [Python] 회문 문자열 검사 (0) | 2023.01.25 |