백준 알고리즘 - 배열 합치기 (11728) [Python]

 

 

 문제

 

www.acmicpc.net/problem/11728

11728번: 배열 합치기

 

 

 

 

 

 

 문제 상황

 

- 정렬된 두 배열을 하나로 합쳐 정렬된 결과물을 출력한다. 

 

 

 

 

 

 

 해결 전략

 

1. 인덱스를 하나씩 탐색하며 더 작은 쪽을 결과물에 담으면 된다.(Merge)의 개념

 

2. Python의 내장 sort(O(NlogN))을 이용한다. 

 

 

 

 

 

 

 코드

 

# merge의 개념으로 접근
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
N_list = list(map(int,input().split()))
M_list = list(map(int,input().split()))
combined = [] # 합쳐진 리스트
i, j = 0, 0 # N의 인덱스, M의 인덱스
while i<N and j<M:
    if N_list[i] < M_list[j]:
        combined.append(N_list[i])
        i += 1
    else :
        combined.append(M_list[j])
        j += 1
combined += N_list[i:] if j == M else M_list[j:]
print(' '.join(list(map(str,combined))))
 
 
# python의 특성을 이용한 방법
from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
N_list = list(map(int,input().split()))
M_list = list(map(int,input().split()))
combined = N_list + M_list
print(' '.join(list(map(str,sorted(combined)))))

 

 

 

 

 

 

 

 

 해설

 

- (Merge)양쪽 인덱스에서 하나씩 관찰하며 크기를 비교하고 담을 것을 정한다. 다 담으면 나머지를 한번에 추가해준다.

 

- (내장함수) sort를 이용해 연산해준다.

 

 

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- 바보같이 그냥 리스트를 출력해놓고 왜 틀린지 몰랐다.. 조건이 띄어쓰기로 하나하나 보여주는 것이다. 출력 조건도 잘 봐야한다.

 

- 직접 리스트를 자르는 것이 아니라 관찰해서 새로 배당하는 것인데 마지막에 남은 리스트를 그냥 N_list로 더해버렸다. 남은 부분을 더했어야 했다.

 

- 속도는 내장함수를 사용한 것이 약 1.5배 빨랐다.