[BaekJoon 9024번] 두 수의 합(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

9024번: 두 수의 합

 

 

[문제 설명]

 

 

여러 개의 서로 다른 정수 S = {a1, a2, …, an} 와 또 다른 정수 K 가 주어졌을 때, S 에 속하는 서로 다른 두 개의 정수의 합이 K 에 가장 가까운 두 정수를 구하시오. 예를 들어, 10 개의 정수

 

S = { -7, 9, 2, -4, 12, 1, 5, -3, -2, 0}

 

가 주어졌을 때, K = 8 에 그 합이 가장 가까운 두 정수는 {12, -4} 이다. 또한 K = 4 에 그 합이 가장 가까운 두 정수는 {-7, 12}, {9, -4}, {5, -2}, {5, 0}, {1, 2} 등의 다섯 종류가 있다.

여러 개의 서로 다른 정수가 주어졌을 때, 주어진 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수에 가장 가까운 두 정수의 조합의 수를 계산하는 프로그램을 작성하시오.

 

 

[입력]

 

 

프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄에 한 개의 테스트 케이스에 해당하는 데이터가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 두 개의 정수 n 과 K (2 ≤ n ≤ 1,000,000, -108 ≤ K ≤ 108 )가 한 개의 공백을 사이에 두고 입력된다. 두 번째 줄에는 n 개의 정수가 하나의 공백을 사이에 두고 주어지며, 각 정수의 최댓값은 108 이고, 최솟값은 -108 이다. 잘못된 데이터가 입력되는 경우는 없다.

 

 

[출력]

 

 

출력은 표준출력(standard output)을 사용한다. 입력되는 테스트 케이스의 순서대로 다음 줄에 이어서 각 테스트 케이스의 결과를 출력한다. 각 테스트 케이스의 출력되는 첫 줄에 입력으로 주어진 n 개의 정수들 중에서 서로 다른 두 정수의 합이 주어진 또 다른 정수 K 에 가장 가까운 두 정수의 조합의 수를 출력한다.

 

 

[입출력 예]

 

 

입력	출력
4 10 8 -7 9 2 -4 12 1 5 -3 -2 0 10 4 -7 9 2 -4 12 1 5 -3 -2 0 4 20 1 7 3 5 5 10 3 9 7 1 5	1 5 1 2

 

 

[문제 풀이]

 

 

서로 다른 두 정수의 합이 K에 가까운 두 정수의 조합의 수를 구해야하는 문제이다.

 

내가 작성한 알고리즘을 간단하게 설명하자면..

 

1. 입력받은 배열을 sort함수를 이용하여 오름 차순 정렬한다.

 

2. 두 개의 변수를 이용하여 두 포인터 알고리즘을 사용한다.

• 두 정수의 합이 K보다 크다면 end 변수를 1씩 감소
• 두 정수의 합이 K보다 크지않다면 start 변수를 1씩 감소
• key, value가 int형인 map에 key에는 |K- 두 정수의 합|과 value에는 갯수를 저장

 

3. key를 오름 차순 정렬하는 map의 첫번째 원소를 확인하면 두 정수의 합이 K에 가까운 값이 몇개인지 알 수 있다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int TC; cin >> TC;
    for(int i = 0; i < TC; ++i) {
        int n; int K; cin >> n >> K;
        vector<int> v;
        for(int j = 0; j < n; ++j) {
            int num; cin >> num;
            v.emplace_back(num);
        }
        sort(v.begin(), v.end());
        
        int start = 0; int end = n - 1;
        map<int, int> m;
        while(start < end) {
            int num = v[start] + v[end];
            if(num > K) {
                end -= 1;
            } else {
                start += 1;
            }
            m[abs(K - num)] += 1;
        }

        for(auto iter = m.begin(); iter != m.end(); ++iter) {
            cout << iter->second << '\n';
            break;
        }
    }
    return 0;
}