[JAVA] 백준 (골드4) 1253번 좋다

링크

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

---

문제 설명

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

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

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

---

입력 예제

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

10
1 2 3 4 5 6 7 8 9 10

---

출력 예제

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

8

---

풀이

이전의 주몽 문제와 유사하다. 다만 같은 숫자가 존재할 수 있다는 조건이 추가되었다.

우선 합이 되는 수를 찾아야 하므로 전체 수에 대해 반복한다. 이때 포인터에 해당하는 start와 end는 처음과 끝 인덱스부터 합이 되는 수를 찾으면서 탐색을 하는데 현재 수에 대한 인덱스는 제외하여야 한다. 현재 수의 인덱스일 경우 start는 다음 인덱스, end는 이전 인덱스로 갱신한다. 다만 둘다 현재 수의 인덱스가 아닐 경우 정답으로 카운트한다.

if (sum == curNum) {
    if (start != i && end != i) {
        count++;
        break;
    }
    
    if (start == i) {
        start++;
    } else if (end == i) {
        end--;
    }
}

코드

//백준
public class Main {

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("src/input.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());  //수의 개수
        long[] numbers = new long[N];  //숫자 배열
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            numbers[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(numbers);  //오름차순 정렬

        int count = 0;

        for (int i = 0; i < N; i++) {
            long curNum = numbers[i];
            int start = 0;
            int end = N - 1;

            while (start < end) {

                long sum = numbers[start] + numbers[end];

                //현재 숫자가 좋은 수일 때
                if (sum == curNum) {
                    if (start != i && end != i) {
                        count++;
                        break;
                    }
					
                    //포인터가 현재 인덱스일 경우
                    if (start == i) {
                        start++;
                    } else if (end == i) {
                        end--;
                    }
                }

                if (sum < curNum) {
                    start++;
                }  else if (sum > curNum) {
                    end--;
                }
            }

        }


        System.out.println(count);
    }
}