114. 좋다 (백준 1253) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/1253

1253번: 좋다

문제

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

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

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

입력

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

출력

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

풀이

전체 숫자가 2000개이므로, 모든 덧셈 조합을 만들어보면 10C2 = 1000*1999개이다.

여기서 이제 숫자가 속해있는지를 탐색해야 하는데

단순히 배열을 사용한다면, n번을 더 탐색해야 해서 횟수가 많아지게 된다.

따라서 복잡하더라도 해시맵을 사용했다.

이때 해시맵을 사용하게 된다면 발생하는 문제가, 0을 더해주는 경우 자기 자신에 관한 처리이다.

0 0 은 자기 자신을 포함하여 불가능하다.

반면 0 0 0 은 0(1) + 0(2) -> 0(3)이 가능하고, 조합을 돌려주면 되니깐 3개 모두 가능하다.

1 0 2의 경우 자기 자신을 포함하기 때문에 1, 2가 불가능하다.

반면 1 0 1의 경우 1(1) + 0 -> 1(2)로 가능하기 때문에 1이 두개 모두 가능하다.

1. 둘다 0인경우 -> 0이 3개가 아니면 더해주지 않기
2. 하나가 0인 경우 -> 나머지 하나가 2개가 아니면 더해주지 않기

처리가 끝난 키값은 삭제함으로써 중복을 방지하였다.

코드

import java.io.BufferedReader;
import java.io.IOException;

import java.io.InputStreamReader;
import java.util.*;

class Main {

    static int N;
    static HashMap<Integer, Integer> maps = new HashMap<>();
    static int[] goods;
    static int answer = 0;
    /**
     * 2000C2*2000 = 2000*1999*1000
     **/

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        goods = new int[N];

        for(int i=0; i<N; i++){
            goods[i] = Integer.parseInt(st.nextToken());

            if(maps.containsKey(goods[i])){
                maps.put(goods[i],maps.get(goods[i])+1);
            }
            else{
                maps.put(goods[i], 1);
            }
        }

        int sum;

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

                sum = goods[i] + goods[j];
                int add;

                if(maps.containsKey(sum)){
                    add = maps.get(sum);

                    //둘다 0일때
                    if(goods[i] == 0 && goods[j] == 0){
                        if(add >= 3){
                            answer = answer + add;
                            maps.remove(sum);
                        }
                    }
                    //1개만 0일때 = 2이상
                    else if(goods[i] == 0 || goods[j] == 0){
                        if(add >= 2){
                            answer = answer + add;
                            maps.remove(sum);
                        }
                    }
                    else{
                        answer = answer + add;
                        maps.remove(sum);
                    }
                }

            }
        }
        System.out.println(answer);
    }
}

결과

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!