[백준] 11728 배열 합치기

🌭 문제 설명

• 정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

---

🍗 제한 사항

---

🎁 입출력 예시

• 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

• 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 10^9보다 작거나 같은 정수이다.

• 첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

---

😎 나의 풀이

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = [] # 답 출력 배열

pos1 = 0 # 후보1
pos2 = 0 # 후보2

while pos1 < N and pos2 < M: # A,B의 pos가 넘지 않을 때 까지 반복
  candidate1 = A[pos1]
  candidate2 = B[pos2]
  
  if candidate1 < candidate2: # 후보로 나온 2개중에 작은 것을 C에 넣어줌
    C.append(candidate1) 
    pos1 += 1 # A의 후보 번호를 1 증가
  else:
    C.append(candidate2)
    pos2 += 1

if pos1 != N: # A가 소진이 안됬을 때
  C.extend(A[pos1: N])  # C에 나머지 있는것을 다 붙여넣어줌
if pos2 != M:
  C.extend(B[pos2: M])
for i in range(N + M):
  print(C[i], end=" ")

1. N ,M을 입력받는다.
2. A와 B도 list로 입력을 받고 답을 출력할 C배열을 만든다.
3. A의 후보 번호를 지정할 pos1을 초기화 , B의 후보 번호를 지정할 pos2를 초기화 한다.
4. while문은 A,B의 후보 번호가 넘기 전까지 반복한다.
5. A의 후보 값을 저장할 candidate1 , B의 후보 값을 저장할 candidate2
6. 두 개의 후보 값중 작은 값을 C 배열에 넣어준다. (정렬 된 값이 들어가야 하기 때문에 작은 값을 넣어준다.)
7. A의 후보 번호 pos1를 +1 해주어 다음 값을 찾는다. (반대의 경우에는 pos2)
8. A가 전부 소진이 안됬을 때는 C에 나머지 값들을 extend로 붙여준다.
9. B도 마찬가지
10. 요구사항에 맞게 출력한다.

---

🧵 다른 풀이

import sys
input = sys.stdin.readline

A,B = map(int,input().split()) # 배열 A의 크기, M의 크기

Anumber = list(map(int, input().split()))
Bnumber = list(map(int, input().split()))
habche = Anumber + Bnumber
habche.sort()
for num in habche:
  print(num, end=" ")

1. 처음에 이 풀이로 채점에 통과했는데 시간제한이 1.5초 길래 나는 1.6초가 나왔는데 통과가 되서 이상하다 싶어서 찾다보니 파이썬으로 풀 시 시간제한 보정이 있어서 통과한 것 이었다.
2. 이 풀이가 직관적이고 간편하지만 시간복잡도 면에서 봤을 때 내가 푼 풀이가 O(N+M)이므로 정렬을 사용해서 효율적이게 풀 수 있다.

---

• 쉽게 풀릴 땐 시간복잡도를 한번 생각해보자!