[백준 1253] 좋다 - java

python도 좋지만 새로운 언어로 java를 사용해보려 한다.

읽는데 문제가 없지만 입출력, 자료구조를 구현하는데 생각보다 애를 먹고있다. 나중에 정리해보려 한다.

문제.

1253번: 좋다

 

N개의 수가 주어지는데, 어떤 수를 다른 두 수의 합으로 나타낼 수 있으면 "좋다" 라고 하기로 한다.

"좋다"의 갯수를 출력하라.

입출력 예시.

<입력 예시>
10
1 2 3 4 5 6 7 8 9 10

<출력 예시>
8

조건.

1 <= N <= 2000

| Ai | <= 1_000_000_000 인 정수 

 

---

풀이.

단순히 두 수의 합을 모두 저장한 뒤 찾아보려고 하면 오답이다.

예를들어 0이 두 개 들어오는 경우 서로 다른 두 수가 없어 답은 0이다.
아래 예시도 같은 결과이다.

3
0 0 1

ans: 0

정렬한 후 탐색하려고 시도했으나 오답이었다.
배열에는 음수도 들어올 수 있기 때문에 앞쪽 두개의 합이 뒤쪽에 나온다고 확신할 수 없다.
음수 + 음수 일때는 두 수보다 앞쪽에
양수 + 양수 일때는 두 수보다 뒤쪽에 위치한다.
음수 + 양수인 경우는 사이에 있는 값이다.

위 처럼 3가지 경우로 나누어 탐색할 수도 있지만
투포인터를 사용하여 각 결과에 따라 포인터를 옮겨주면 최대 O(n)의 시간에 값이 존재하는지 확인할 수 있다.

 

제출 코드

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
        
		List<Long> arr = new ArrayList<>();
		for (int i=0; i<n; i++) arr.add(sc.nextLong());
		Collections.sort(arr); // 정렬
        
		int ans = 0;
		for (int i=0; i<n; i++) {
			Long K = arr.get(i); // K를 찾는것
			int s = 0;
			int e = n-1;
			while (s < e) { // s와 e를 조절하며 탐색한다.
				Long t = arr.get(s) + arr.get(e);
				if (t < K) s++;
				else if (t > K) e--;
				else {
					if (s!=i && e!=i) { // 자기자신을 합으로 하면 pass
						ans++;
						break;
					}
					else if (s==i) s++;
					else e--;
				}
			}
		}
		System.out.println(ans);
		sc.close();
	} // main
}

---

+ 파이썬에서는 기본으로 사용되는 list를 import 하여 사용해야 한다.
+ int대신 long을 사용해야 한다.
생각보다 다른구현은 없어 나름 쉽게 해낼 수 있었다.