[BaekJoon] 1253 좋다 (Java)

1.  문제 링크

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

2.  문제

요약

• N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 "좋다(GOOD)"고 합니다.
• 수의 위치가 다르면 값이 같아도 다른 수로 취급합니다.
• N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 2,000보다 작거나 같은 수의 개수 N이 주어지고 두 번째 줄에는 절댓값이 1,000,000,000보다 작거나 같은 i번째 수를 나타내는 $A_i$가 N개 주어짐니다.
• 출력: 첫 번째 줄에 좋은 수의 개수를 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static ArrayList<Integer> seq;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		seq = new ArrayList<>();
		for(int i = 1; i <= N; i++) seq.add(scanner.nextInt());
	}
	
	static void solution() {
        Collections.sort(seq);
		ArrayList<Integer> temp = new ArrayList<>();
		temp.addAll(seq);
		int ans = 0;
		for(int i = 0; i < seq.size(); i++) {
			temp.remove(i);
			int L = 0, R = N - 2;
			while(L < R) {
				int sum = temp.get(L) + temp.get(R);
				if(sum  == seq.get(i)) {
					ans++;
					break;
				}
				if(sum > seq.get(i)) {
					R--;
				} else {
					L++;
				}
			}
			temp.add(i, seq.get(i));
		}
		System.out.println(ans);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}

4.  접근

• 이 문제는 투포인터를 이용하여 구할 수 있는 문제입니다.

  주어진 수들을 오름차순으로 정렬하고 각 수에 대해서 다른 두 수를 더했을 때 만들어지는지 투포인터를 이용하여 확인한 후 그렇다면 좋은 수의 개수를 늘려주어 좋은 수의 개수를 찾습니다.

• 주어진 수들을 ArrayList에 담고 이를 오름차순으로 정렬합니다.
• temp라는 ArrayList를 하나 만드는데 이는 각 수가 좋은 수인지 확인할 때, 다른 두 수를 탐색할 때 사용하는 ArrayList에 그 수는 들어있으면 안되기 때문에 그 수를 뺀 수들만 넣어주기 위해 생성합니다. temp는 주어진 수들을 오름차순으로 정렬한 값들로 초기화합니다.
• 주어진 수들을 담은 ArrayList에 있는 값들을 하나씩 보면서 그 수가 좋은 수가 될 수 있는지 확인합니다.
  • temp에서 좋은 수인지 확인하고 있는 수를 제거해줍니다.
  • 투포인터에서 왼쪽 포인터와 오른쪽 포인터를 나타내는 변수 L, R을 생성하고 각각 최소값인 0과 최대값인 N - 2로 초기화합니다.
  • L이 R보다 크거나 같아지는 시점 전까지 포인터들을 이동해보며 현재 확인하고 있는 수가 좋은 수인지 확인합니다.
    • 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 수를 더하고 더한 수를 현재 확인하고 있는 수와 비교하여 포인터를 옮기거나 좋은 수의 개수를 늘리고 다음 수를 확인합니다.
      1. 만약 더한 수가 현재 확인하고 있는 수와 같다면 이 수는 좋은 수가 맞기 때문에 좋은 수의 개수를 나타내는 변수 ans의 값을 1 증가시키고 다음 수를 확인하기 위해 while 반복문을 빠져나갑니다.
      2. 만약 더한 수가 현재 확인하고 있는 수보다 크다면 더한 수를 더 줄여야하기 때문에 오른쪽 포인터를 왼쪽으로 이동시킵니다.
      3. 만약 더한 수가 현재 확인하고 있는 수보다 작다면 더한 수를 더 늘려야하므로 왼쪽 포인터를 오른쪽으로 이동시킵니다.
  • 현재 확인하고 있는 수에 대해 좋은 수인지 판별을 마쳤다면 그 수를 다시 temp에 넣어 다음 수를 확인할 때 이용합니다.