[백준]1253번 좋다 - C++/Java

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

1253번: 좋다

문제

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

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

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

입력

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

출력

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

---

    두 개의 수를 더해 다른 한 수를 만드는 경우 정렬이 된 배열에서 두 매개변수를 조절해가면서 이분 탐색을 하면 찾을 수 있다. 다만 유의할 점은 자기 자신은 제외한 다른 두 수 이기 때문에 두 매개변수가 자신을 가리키면 넘어가는 것이다.

#include <iostream>
#include <algorithm>

using namespace std;
int N,cnt = 0;
int arr[2001];
int main() {
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];

	sort(arr, arr + N);
	
	for (int i = 0; i < N; i++) {
		int s = 0;
		int e = N - 1;
		while (s != e) {
			if (s == i) s++;
			else if (e == i) e--;
			else {
				int temp = arr[s] + arr[e];
				if (temp == arr[i]) {
					cnt++;
					break;
				}
				else if (temp > arr[i]) e--;
				else s++;
			}
		}

	}
	cout << cnt;
	return 0;
}

package test;
import java.util.*;

public class Main{
	static int[] arr;
	static int N,cnt=0;
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N];
		for(int i = 0 ; i< N;i++) {
			arr[i] = sc.nextInt();
		}
		
		Arrays.sort(arr);
		
		for (int i = 0; i < N; i++) {
			int s = 0;
			int e = N - 1;
			while (s != e) {
				if (s == i) s++;
				else if (e == i) e--;
				else {
					int temp = arr[s] + arr[e];
					if (temp == arr[i]) {
						cnt++;
						break;
					}
					else if (temp > arr[i]) e--;
					else s++;
				}
			}

		}
		System.out.println(cnt);
	}
}

---

    처음에는 자신보다 작은 수들로 덧셈을 진행하였으나 생각해보니 음수도 존재하기 때문에 배열의 처음과 끝에서부터 시작을 해야 된다는 것을 깨달았다. 또한 자기 자신을 제외하는 것까지 고려하고 나니 문제가 쉽게 풀렸다. 이분 탐색 문제를 최근에 안 푼 것 같아 처음에는 난이도가 조금 높은 이분 탐색을 선정하였지만 그 문제를 어떻게 이분 탐색으로 풀지 감이 잡히지 않았다. 그래서 조금 쉬운 난이도의 이분 탐색을 하니 금방 풀렸다. 난이도를 점차 높여가 이분 탐색적 생각에 익숙해져야겠다!

    Java의 경우 항상 변수 선언이 제일 어려운 것 같다. 배열의 선언 역시 처음에 int[] arr = new int[2001] 로 했다가 정렬을 하니 이상하게 되어 변수 N을 입력받고 arr= new int [N];으로 선언하였다. C++ 문제풀이 방식보다 깔끔하게 저장공간을 관리할 수 있는 것 같다. 정렬의 경우 Arrays.sort()를 활용하면 정렬이 오름차순으로 된다. 나머지 부분을 C++과 동일하다.