[Python-CodingTest] 3-4. 두 리스트 합치기

두 리스트 합치기

문제 정리

입력

10
1 10 27 39 50 61 65 70 93 93 
7
7 51 65 66 70 82 93 

처리 과정

1. 포인터 변수 초기화
2. 빈 리스트 생성
3. p1이 n이 되거나 p2가 m이 되면 while문 종료
4. lst_1과 lst_2의 각각의 요소들을 비교하며 더 작은 요소를 결과 리스트인 res에 추가
5. 해당 포인터는 +1
6. p1 혹은 p2가 n 또는 m과 같아졌다면 나머지 요소들은 그대로 이어붙이기 (이미 정렬되어있기 때문)

출력

1 7 10 27 39 50 51 61 65 65 66 70 70 82 93 93 93

내 답

import sys
sys.stdin = open("./input/in4.txt", "rt")

n = int(input())
lst_1 = list(map(int, input().split()))
m = int(input())
lst_2 = list(map(int, input().split()))

lst = lst_1+lst_2
lst.sort()

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

위 방법은 시간복잡도가 nlogn이지만, 입력된 두 개의 리스트가 이미 오름차순 정렬되어 있다는 특징으로 시간복잡도가 n인 효율적인 코드를 작성할 수 있다.

풀이

import sys
sys.stdin = open("./input/in4.txt", "rt")

n = int(input())
lst_1 = list(map(int, input().split()))
m = int(input())
lst_2 = list(map(int, input().split()))

p1=p2=0 # 포인터 변수 초기화
res=[] # 빈 리스트 (결과 리스트)

while p1<n and p2<m:
    if lst_1[p1]<=lst_2[p2]:
        res.append(lst_1[p1])
        p1+=1
    else:
        res.append(lst_2[p2])
        p2+=1

if p1<n:
    res+=lst_1[p1:] # p1부터 끝까지 이어붙이기
else:
    res+=lst_2[p2:] # p1부터 끝까지 이어붙이기

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

정리

• 빈 리스트 생성: lst=[]
• 리스트에 추가: lst.append()
• res 리스트에 lst 리스트의 2번째 인덱스부터 마지막까지 이어붙이기: res+=lst[2:]

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기