[백준] 17124 - 두 개의 배열 (C++)

https://www.acmicpc.net/problem/17124

정수 배열 A와 B가 있고, A는 총 n개의 서로 다른 양의 정수를 포함하고 B는 총 m개의 서로 다른 양의 정수를 포함한다. A와 B를 이용해 길이가 n인 새로운 배열 C를 만드는 문제다.

• C[i] = 배열 B에 있는 값 중 A[i]에 가장 가까운 값(절대값 차이가 가장 작은 값)
• 이 조건을 만족하는 값들이 여럿 있는 경우, 그 중 가장 크기가 작은 값

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ T ≤ 10
• 1 ≤ n, m ≤ 1,000,000 (각 원소의 값은 1 이상 1,000,000,000 이하)

 

C 배열의 길이는 n이고, A 배열의 원소 값에 가장 가까운 값을 B 배열에서 찾아서 넣어야 한다.

n개 중 하나하나마다 m개의 원소에서 값을 찾는 건 1000000 × 1000000이라 시간 제한을 초과하게 된다.

이분탐색을 적용하면 1000000 × O(log 1000000)의 시간 안에 처리할 수 있다.

 

원소의 합이 int 범위를 넘을 수 있어서 long long int를 사용해야 한다.

 

C++ algorithm 헤더에 있는 함수 중 lower_bound()와 upper_bound()는 이분탐색이 적용된다. 이 문제에서 사용한 건 아니지만 이참에 정리해둬야겠다. 

• lower_bound(start, end, target)
  • 적용할 배열이 오름차순으로 정렬된 상태여야 함
  • 찾고자 하는 값 이상이 처음으로 나타나는 Iterator를 리턴
    
    • 찾고자 하는 값이 주어진 데이터들 보다 크면 end() Iterator를 리턴
    • 찾고자 하는 값이 주어진 데이터들 보다 작으면 begin() Iterator를 리턴

• • 인덱스를 구하기 위해선 리턴값에서 배열의 시작 주소를 빼야 함
  • lower_bound(start, end, target, greater<>())
    • 내림차순 정렬로 target보다 이하인 것 중 최대인 Iterator를 리턴

// vector 사용
int lower_idx = lower_bound(vec.begin(),vec.end(),x) - vec.begin();

// int 배열 사용
int lower_idx = lower_bound(arr, arr+5, x) - arr;

• upper_bound(start, end, target)
  • 적용할 배열이 오름차순으로 정렬된 상태여야 함
  • 찾고자 하는 값보다 큰 값이 처음으로 나타나는  Iterator를 리턴
    • 찾고자 하는 값이 주어진 데이터들 보다 크면 end() Iterator를 리턴
    • 찾고자 하는 값이 주어진 데이터들 보다 작으면 begin() Iterator를 리턴

• • 인덱스를 구하기 위해선 리턴값에서 배열의 시작 주소를 빼야 함
  • upper_bound(start, end, target, greater<>())
    • 내림차순 정렬로 target보다 미만인 것 중 최대인 Iterator를 리턴

// vector 사용
int upper_idx = upper_bound(vec.begin(),vec.end(),x) - vec.begin();

// int 배열 사용
int upper_idx = upper_bound(arr, arr+5, x) - arr;

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. T 입력 받기 (테스트 케이스 T개)
   1. n, m 입력 받기
   2. A 배열과 B 배열 정보 각각 입력 받고 B 배열 정렬하기
   3. A와 B로 C 배열 만들기
   4. C 배열의 모든 원소의 합을 출력

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int t;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> t;
    while (t--) {
        int n,m,x;
        long long int sum = 0;
        vector<int> a,b;
        cin >> n >> m;
        for (int i=0; i<n; i++) {
            cin >> x;
            a.push_back(x);
        }
        for (int i=0; i<m; i++) {
            cin >> x;
            b.push_back(x);
        }
        sort(b.begin(),b.end());

        for (int i=0; i<n; i++) {
            long long int l=0, r=m-1, mid;

            while (l+1<r) {
                mid = (l+r)/2;

                if (b[mid]<a[i]) l=mid;
                else r=mid;
            }

            sum += (abs(a[i]-b[l]<=abs(a[i]-b[r]))? b[l] : b[r]);
        }

        cout << sum << '\n';
    }
}