1253 좋다 [JAVA]

문제 분석

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

N개의 수가 주어지고 각 수마다 해당 숫자를 자신을 제외한 서로 다른 두 수의 합으로 만들어낼 수 있는지 판단하고 그렇다면 좋은 수로 여긴다.

이때 좋은 수의 갯수를 구하는 문제.

 

N은 2000까지, 값은 절댓값기준 10억 이하 정수

N이 작기에 n^2의 풀이도 통과될 수 있다.

 

처음엔 간단하게 for loop를 2번 돌리며 가능한 모든 수의 합을 Set에 넣고 배열에 대해서 있으면 ans ++ 하는 방식으로 구현했었다. 즉, 0~n-2의 인덱스 i에 대해 i+1 ~ n-1의 인덱스와의 합을 Set에 저장했다.

 

그런데, 생각해봐야 하는 부분이 있다.

0 + k 는 k다. 여기서, 합쳐진 결과 k는 자기자신을 사용하였기에 문제의 조건에 어긋난다.

하지만, 만약 다른 위치에 동일한 값인 k가 있다면 합쳐진 결과값 k는 만들어낼 수 있는 수가 된다.

 

또, 0 + 0 = 0 이다. 위와 같은 논리로 0은 서로다른 위치에 0이 최소 3개 이상 있어야 만들어낼 수 있다.

 

따라서, for loop을 n^2 순회하며 고려해야 하는 사항은

arr[i], arr[j] 모두 0인 경우 -> 0+k 계산에 중복될테니 넘긴다.

둘 중 하나가 0이고 0이 아닌 숫자 k가 배열 내에서 유일한 경우 -> 자기 자신으로만 구성되는 합이니 넘긴다.

 

이렇게 두가지다.

위의 경우를 제외한 나머지 합들을 Set에 저장해주고

 

각 배열의 원소에 대해 0이 아닌 수라면 Set에 있는지

0이라면 배열 내 0의 갯수가 3개 이상인지 혹은 Set에 0이 들어있는 지 (+a -a의 합은 0이 된다.)

 

이 두가지 경우에 대해서 확인하고 좋은 수를 판단해주면 된다.

 

코드 자체는 간단하니 직접 확인해보자.

 

코드

import java.util.*;

public class Main {


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<Integer> madeNum = new HashSet<>();
        int n = sc.nextInt();
        int[] arr = new int[n];
        int zeroCnt = 0;
        Set<Integer> targetSet = new HashSet<>();
        Set<Integer> duplicatedSet = new HashSet<>();

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            if(targetSet.contains(arr[i]))
                duplicatedSet.add(arr[i]);
            else
                targetSet.add(arr[i]);

            if(arr[i] == 0)
                zeroCnt++;
        }

        for (int i = 0; i < n-1; i++) {
            for (int j = i+1; j < n; j++) {
                if(madeNum.contains(arr[i] + arr[j]))
                    continue;
                if(arr[i] == 0 && arr[j] == 0){
                    //all zero
                    continue;
                }else if(arr[i] == 0 && !duplicatedSet.contains(arr[j])){
                    //cannot add cause it is selfmade num
                    continue;
                }else if (arr[j] == 0 && !duplicatedSet.contains(arr[i])){
                    //cannot add cause it is selfmade num
                    continue;
                }

                madeNum.add(arr[i] + arr[j]);

            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if(arr[i] == 0){
                if(zeroCnt >2 || madeNum.contains(0))
                    ans++;
            }else if(madeNum.contains(arr[i])){
                ans++;
            }
        }

        System.out.println(ans);


    }


}