백준 1253. 좋다

문제 백준 1253. 좋다

좋긴 뭐가 좋냐

문제

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

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

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

입력

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

출력

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

풀이

이 문제에 대한 다른 포스팅도 그렇고, 책에 나와있는 해설에도 이 문제는 설명이 불친절하고 부실하다고 한다. 조건이 하나가 추가되어야 하는데 자기 자신을 좋은 수 만들기에 포함하면 안된다가 빠졌다.

다른 투포인터 문제와 다를게 없다.
우선 주어지는 N개의 수는 정렬된 입력이라는 말이 없으니, 값들의 합을 구하려면 정렬을 해주어야 한다. 정렬을 하고 양 끝에서부터 두 개의 값을 합하여 좋은 수를 만들 수 있는지 판단해나가면 된다.

풀이 코드 python

n = int(input()) #최소 한개
numbers = list(map(int,input().split()))
numbers.sort()
result = 0

for k in range(len(numbers)):
    i = 0
    j = n-1

    target = numbers[k]

    while (i < j):
        if numbers[i] + numbers[j] == target:
            if i != k and j != k:
                result += 1
                break
            elif i == k:
                i += 1
            elif j == k:
                j -= 1
        elif numbers[i] + numbers[j] < target:
            i += 1
        else:
            j -= 1

print(result)

풀이 코드 java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj1253 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer stk = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(stk.nextToken());
        }
        Arrays.sort(arr);

        int result = 0;

        for (int k = 0; k < n; k++) {
            int i = 0;
            int j = n-1;

            while (i < j) {
                if (arr[i] + arr[j] == arr[k]) {
                    if (i != k && j != k) {
                        result++;
                        break;
                    }
                    else if (i == k) {
                        i++;
                    }
                    else if (j == k) {
                        j--;
                    }
                }
                else if (arr[i] + arr[j] < arr[k]) {
                    i++;
                }
                else {
                    j--;
                }
            }
        }
        System.out.println(result);
    }
}