[BOJ S4][C++] 백준 14911번: 궁합 쌍 찾기

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

14911번: 궁합 쌍 찾기

 

문제

첫째 줄에 주어진 여러 개의 정수 중에서 합이 둘째 줄에 주어진 수와 같은 서로 다른 위치에 있는 두 수의 쌍을 모두 출력하고 맨 아래에 이 쌍의 개수를 이어서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 빈 칸으로 구분된 정수가 2개 이상, 10개 이하 주어진다. 둘째 줄에는 정수가 하나 주어진다. 주어지는 정수는 100,000보다 작거나 같은 자연수이다.

출력

찾은 수의 쌍을 한 줄에 하나씩 출력하고 맨 아랫 줄에 그러한 쌍의 개수를 출력한다.

구성은 같지만, 순서가 다른 쌍 (a, b)와 (b, a)는 쌍 하나로 하며, a ≤ b인 쌍을 출력한다.

쌍이 여러 개인 경우에는 사전 순으로 출력한다. (a, b)가 (c, d)보다 사전 순으로 앞서는 기준은 a < c이거나, a == c 이면서, b < d 인 것이다.

 

풀이

입력 갯수가 주어지지 않아서 인터넷을 참고했다.

입력받은 수들을 map으로 저장하여 각 값이 몇개씩 있는지를 값의 순서대로 저장한다.

이후 이 맵을 앞에서부터 돌면서 순서쌍을 이루는 숫자가 있는지 체크하고 갯수를 줄여나가는 식으로 카운트 및 출력

// Authored by : seondal
// Co-authored by : -

// #include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    map<int, int> cnt; // cnt[i] = i의 갯수
    
    int n;
    while(cin >> n)
        cnt[n]++;
    int target = n;

    int ans = 0;
    for(auto i: cnt) {
        int need = target - i.first;
        
        cnt[i.first]--;
        if(cnt[need] > 0) {
            cnt[need]--;
            cout << i.first << " " << need << "\n";
            ans++;
        }
    }
    cout << ans;
    
    
    return 0;
}

/*
 */