BOJ(백준) 11728[배열 합치기]

안녕하세요! 오늘은 백준의 11728번 문제인 “배열 합치기” 문제를 함께 풀어보겠습니다. 이 문제는 두 개의 정렬된 배열을 하나의 정렬된 배열로 합치는 문제입니다. 함께 문제를 해결해보도록 하죠!

 

1. 문제 설명

 

1. 두 개의 정렬된 배열 A와 B가 주어집니다.

2. 이 두 배열을 합쳐서 하나의 정렬된 배열을 만들어야 합니다.

 

문제URL : https://www.acmicpc.net/problem/11728

2. 접근법

1) 입력받기: 배열 A와 배열 B의 크기와 요소들을 입력받습니다.

2) 병합: 두 배열을 정렬된 상태로 병합합니다.

3) 결과 출력: 병합된 배열을 출력합니다.

3. 정답 코드

import sys
input = sys.stdin.readline

N, M = map(int, input().split())  # 첫 번째 줄에서 N(배열 A의 크기)과 M(배열 B의 크기)을 읽어온다.

A = list(map(int, input().split()))  # 두 번째 줄에서 배열 A의 요소들을 읽어온다.
B = list(map(int, input().split()))  # 세 번째 줄에서 배열 B의 요소들을 읽어온다.

ans = []        # 정렬된 결과를 담을 리스트
i = 0; j = 0    # 두 배열 A와 B의 인덱스를 각각 나타내는 변수 초기화

while i < N and j < M:      # 두 배열 중 하나의 끝에 다다를 때까지
    if A[i] < B[j]:         # 배열 A의 현재 요소가 배열 B의 현재 요소보다 작으면
        ans.append(A[i])    # 배열 A의 현재 요소를 결과 리스트에 추가
        i += 1  
    else:                   # 배열 B의 현재 요소가 배열 A의 현재 요소보다 작거나 같으면
        ans.append(B[j])    # 배열 B의 현재 요소를 결과 리스트에 추가
        j += 1  

# 배열 A 또는 배열 B에 남은 요소가 있는 경우 처리
if i != N:              # 배열 A에 남은 요소가 있으면
    ans.extend(A[i:])   # 배열 A의 남은 요소들을 결과 리스트에 추가

if j != M:              # 배열 B에 남은 요소가 있으면
    ans.extend(B[j:])   # 배열 B의 남은 요소들을 결과 리스트에 추가

print(*ans)             # 결과 리스트를 공백으로 구분하여 출력

 

4. 코드 설명

1) 입력받는 부분

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 N(배열 A의 크기)과 M(배열 B의 크기)을 입력받습니다.

• 두 번째 줄에서 배열 A의 요소들을, 세 번째 줄에서 배열 B의 요소들을 입력받습니다.

2) 병합

• 두 배열 A와 B를 순차적으로 비교하면서 더 작은 값을 결과 리스트 ans에 추가합니다.

• 한 배열이 끝나면 남은 다른 배열의 요소들을 결과 리스트에 추가합니다.

3) 결과 출력

• 최종 병합된 배열을 공백으로 구분하여 출력합니다.

 

***

if i != N:              # 배열 A에 남은 요소가 있으면
    ans.extend(A[i:])   # 배열 A의 남은 요소들을 결과 리스트에 추가

if j != M:              # 배열 B에 남은 요소가 있으면
    ans.extend(B[j:])   # 배열 B의 남은 요소들을 결과 리스트에 추가

 

이 부분의 코드가 필요한 이유는?

 

두 배열 A와 B를 병합하는 과정에서 while i < N and j < M: 루프를 사용합니다. 이 루프는 두 배열 중 하나라도 끝에 도달하면 종료됩니다. 따라서, 두 배열 중 하나는 끝에 도달했지만 다른 배열은 아직 끝에 도달하지 않았을 수 있습니다.

 

예를 들어, 배열 A와 배열 B가 다음과 같다고 가정해봅시다:

 

• A = [1, 3, 5]

• B = [2, 4, 6, 8]

 

while 루프를 통해 병합 과정을 진행하면 다음과 같은 순서로 요소가 ans 리스트에 추가됩니다:

 

1] A[0] (1) < B[0] (2) 이므로 ans = [1], i = 1

2] A[1] (3) > B[0] (2) 이므로 ans = [1, 2], j = 1

3] A[1] (3) < B[1] (4) 이므로 ans = [1, 2, 3], i = 2

4] A[2] (5) > B[1] (4) 이므로 ans = [1, 2, 3, 4], j = 2

5] A[2] (5) < B[2] (6) 이므로 ans = [1, 2, 3, 4, 5], i = 3

 

이 시점에서 배열 A는 끝에 도달했지만 배열 B는 아직 두 개의 요소 [6, 8]이 남아 있습니다. 따라서, while 루프가 종료됩니다.

 

루프 종료 후 if i != N:와 if j != M: 부분이 실행되어 남은 요소들을 ans 리스트에 추가합니다:

 

• if i != N:는 조건을 만족하지 않으므로 실행되지 않습니다.

• if j != M:는 조건을 만족하므로 B[j:] 즉, [6, 8]이 ans 리스트에 추가됩니다.

 

최종적으로 ans = [1, 2, 3, 4, 5, 6, 8]이 됩니다.

 

따라서 이 부분은 두 배열 중 하나가 끝에 도달한 이후에도 남아 있는 요소들을 결과 리스트에 포함시키기 위해 필요합니다. 이로써 모든 요소가 정렬된 상태로 병합됩니다.

 

***

 

5. Github으로 확인

coTest/BOJ/BOJ01_05_05_11728.py at main · pcy4196/coTest