문제

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

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

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

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

---

입력

첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

---

출력

좋은 수의 개수를 첫 번째 줄에 출력한다.

---

풀이

접근방법

시간제한 2초, 메모리 256MB이다.

N의 크기는 충분히 작다.
하지만 숫자의 범위가 매우 크다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

두 개의 수의 합이 입력에 있는지를 가장 단순하게 확인하는 방법은 3중 반복문을 이용하는 방법이 있다. 하지만 그 경우 O(N^3)이 되어 2초 안에 통과할 수 없다.

• 해결 방안1. 정렬과 이분 탐색을 이용하기.
  -> 대부분 이런 방식으로 접근한다. 다른 블로그를 참조하자.
• 해결 방안2. Map과 Set을 적절히 이용하기.
  -> 아래 접근 방법을 확인하자.

HashMap, HashSet을 이용하면 O(1)에 삽입과 탐색이 가능하다.
즉 이중 For 문, O(N^2) 문제라고 생각할 수 있다. (시간 충분)
또한 HashMap을 통해 입력으로 주어진 수만 고려하기 때문에 메모리 또한 충분하게 사용 가능하다.

- Logic

1.입력으로 주어진 수들을 배열에 모두 저장한다.
	1-1. 입력으로 주어진 수들이 몇번 등장했는지도 모두 저장한다.
2. 중첩 반복문을 수행하며 두 수의 합이 입력에 있었는지 확인한다.
(해당 숫자가 여러개 존재하는 경우가 있으므로, 해당 경우를 고려해야한다.)
	2-1. 두 수의 합이 입력값에 있었다면, 어떤값인지 기록해 둔다.
3. 기록된 값이 입력에서 몇 번 주어졌는지 모두 더한다.

• 이해를 돕기 위한 입력값 힌트

입력
10
1 2 3 4 5 6 7 8 9 10

10은 1+9, 2+8... 등 여러 개의 경우가 존재한다.
하지만 좋은 숫자는 '10' 1개이다. (따라서 Logic 2-1 과 3이 필요하다)

입력
10
1 2 3 4 5 6 7 8 10 10

위의 예제와 비슷하다. 다만 2+8로 Index9의 10과 Index10의 10을 만들 수 있다.
즉 '10'이라는 숫자는 동일하지만 좋은 숫자는 2개 발생한다.
(따라서 Logic 2-1 과 3이 필요하다)

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Main {

	static int N;
	static int[] arr;
	static Map<Integer, Integer> map;

	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		N = stoi(in.readLine());
		arr = new int[N];
		map = new HashMap<>();
		String[] splitedLine = in.readLine().split(" ");
		for (int i = 0; i < N; ++i) {
			int num = stoi(splitedLine[i]);
			arr[i] = num;
			map.merge(num, 1, (oldValue, newValue) -> oldValue + 1);
		}

		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < N - 1; ++i) {
			int first = arr[i];
			map.put(first, map.get(first) - 1); // 해당 숫자의 카운트를 내린다.
			for (int j = i + 1; j < N; ++j) {
				int second = arr[j];
				map.put(second, map.get(second) - 1); // 해당 숫자의 카운트를 내린다.
				if (map.getOrDefault(first + second, 0) > 0)// 더한 숫자가 입력에 있는경우
					set.add(first + second);

				map.put(second, map.get(second) + 1); // 원상복구
			}
			map.put(first, map.get(first) + 1); // 원상복구
		}
		
		int result = 0;
		for(int i : set)
			result += map.get(i);
		System.out.println(result);
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}