[1253] 좋다

🔗 문제 링크

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

🔍 문제 설명

N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.

N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.

수의 위치가 다르면 값이 같아도 다른 수이다.

⚠️ 제한사항

• $(1 ≤ N ≤ 2,000)$

• $(|A_i| ≤ 1,000,000,000, A_i는 정수)$

---

🗝 풀이 (언어 : Java)

N이 2000 이하라, $O(N^2)$으로 풀 수 있다. 다찾으면 $O(N^3)$이지만, 차이로 짝이되어 정답을 만드는 것이 가능한 숫자를 Set에 넣어, 뒤에서 발견하도록 했다. 정렬한 배열로 투포인터를 이용해$O(NlogN)$으로 푸는 방법도 있는데, 다음번엔 이 방법으로 풀도록 연습하자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Main {
    private static int countGoodCase(int n, int[] nums) {
        int answer = 0;
        for (int i = 0; i < n; i++)
            answer += (isGood(n, nums, i, nums[i])) ? 1 : 0;
        return answer;
    }
    // 한가지 케이스라도 찾았는지 여부
    private static boolean isGood(int n, int[] nums, int i, int target) {
        // 짝숫자를 빨리 찾기위한 Map
        Set<Integer> set = new HashSet<>();
        for (int j = 0; j < n; j++) {
            if (i == j) // 더할 두 숫자가 같은 수를 가르키는 경우 제외
                continue;
            // 지나간 수와 더해서 target 숫자를 만들 수 있는 숫자 발견, 알리고 중단
            if (set.contains(nums[j]))
                return true;
            // 못만드는 경우 해당 수와 짝이 되는 수를 수배목록에 추가
            else
                set.add(target - nums[j]);
        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int[] nums = new int[n];
        for (int i = 0; i < n; i++)
            nums[i] = Integer.parseInt(st.nextToken());
        br.close();
        System.out.println(countGoodCase(n, nums));
    }
}