[백준] 좋다 1253번 (c++) Map

출처 : https://www.acmicpc.net/problem/1253

풀이 방법

문제의 설명이 모호해서 시간이 들었다.

헷갈린 부분 명확하게 정리

• 같은 수가 입력으로 여러 개 들어올 수 있다.
  
  • 같은 수의 위치가 다르면 좋은 수를 카운팅 할 때 같은 수만큼 추가해 주어야 한다.
• 음수가 들어올 수 있다.
• 0이 들어올 때 주의해야 한다.

Map을 이용해서 두 수의 합이 입력으로 들어온 수인지, 입력으로 해당 수가 몇 개 있는지 확인해서 answer에 더해주었다.

또한 한 번 좋은 수로 선택된 수를 중복으로 더하지 않기 위해 더해진 수의 Map값을 0으로 설정했다.

 

#include <iostream>
#include <map>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> numbers;
map<int, int> frequency;

int main() { 
    int n;
    cin >> n;

    // 입력 처리
    numbers.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> numbers[i];
        frequency[numbers[i]]++;
    }

    // 정렬된 상태로 탐색
    sort(numbers.begin(), numbers.end());

    int cnt = 0;

    // 두 수의 합을 탐색
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int a = numbers[i], b = numbers[j];
            int sum = a + b;

            // 합이 범위를 벗어나면 무시
            if (sum > 1000000000 || sum < -1000000000) continue;

            // 조건에 따라 처리
            if (a == 0 && b == 0) {
                if (frequency[0] >= 3) {
                    cnt += frequency[0];
                    frequency[0] = 0; // 방문 처리
                }
            } else if (a == 0 || b == 0) {
                if (frequency[sum] >= 2) {
                    cnt += frequency[sum];
                    frequency[sum] = 0; // 방문 처리
                }
            } else if (frequency.count(sum) && frequency[sum] >= 1) {
                cnt += frequency[sum];
                frequency[sum] = 0; // 방문 처리
            }
        }
    }

    cout << cnt;
    return 0;
}