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는 정수)

 

[출력]

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

 

[예제 입력 1]

10
1 2 3 4 5 6 7 8 9 10

 

[예제 출력 1]

8

---

풀이

 경우의 수를 고려해야 되는 문제이다. 문제 해결을 위해 입력 받은 수를 ArrayList와 HashMap에 모두 저장하고 ArrayList를 이중 for문을 통해 돌며 뽑힌 두 수의 합이 HashMap 상에 존재하면 좋은 수로 판단을 해 답에 추가하면 된다.

 하지만 문제에서는 동일한 수가 여러 개 존재할 수 있고, 문제 언급 상 위치가 다르면 다른 수로 판단하기 때문에 이런 중복의 수를 처리해야 한다. 우선 이 문제에 대한 해결 방법은 ArrayList에는 단순히 중복을 제외한 수들로만 채우고,  HashMap에는 해당 수의 개수도 같이 저장하여 그 수가 좋은 수로 판단되면 HashMap에 저장된 수의 개수를 답에 포함하여 해결하면 된다.

 또 다른 문제는 0에 대한 고려이다. 앞선 문제의 해결로 특정 수가 여러 개고 그 수가 좋은 수면 해당 개수를 모두 답에 추가하면 되지만, 만약 수의 조합을 찾는 과정에서 한 쪽이 0이면 문제가 생긴다. 만약 한 쪽이 0이고 다른 수가 A라고 했을 때 두 수의 합은 당연히 A이고, HashMap 상에서 A의 개수가 1개라 했을 때 이는 답에 추가하지 못한다. 왜냐면 그 한 개의 A는 바로 자신이고, 좋은 수는 다른 두 수의 합으로 표현되어야 하기에 답 추가의 조건을 만족하지 못하기 때문이다. 그렇기에 이를 조건문을 통해 따로 처리하여, 한 쪽이 0인 경우 A쪽의 개수가 2 이상인 경우에만 그 값을 그대로 답으로 가져올 수 있게 처리했다. 이는 양 쪽이 모두 0인 경우에도 동일하여, 0의 개수가 3개 이상인 경우에만 개수를 답에 추가하도록 했다.

 최종적으로 하나의 수에 대해 개수를 답에 추가하면, 개수를 0으로 초기화하여 이후 중복 상황에서 답이 추가되지 않도록 배제했다.

public class Main {

    static int N, answer=0;
    static ArrayList<Long> numbers = new ArrayList<>(); //중복배제 수 저장
    static HashMap<Long, Integer> map = new HashMap<>(); //<수, 개수> 저장

    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());

        while(st.hasMoreTokens()){
            Long number = Long.parseLong(st.nextToken()); //수 입력받음

            if(map.containsKey(number))//이미 중복된 수인 경우
                map.replace(number, map.get(number)+1);
            else{//새로운 수인 경우
                map.put(number, 1);
                numbers.add(number);
            }
        }

        for(int i=0;i<numbers.size();i++){
            Long num1 = numbers.get(i);
            
            if(num1==0){//한쪽이 0인 경우
                if(map.get(num1)>2){//0+0 에 대해
                    answer+=map.get(num1);
                    map.replace(num1, 0);
                }

                for(int j=i+1;j<numbers.size();j++){
                    Long num2 = numbers.get(j);

                    if(map.get(num2)>1){
                        answer+=map.get(num2);
                        map.replace(num2, 0);
                    }
                }
            }
            else{//한쪽이 0이 아닌 경우
                if(map.get(num1)>=2&&map.containsKey(num1*2)){//자신이 여러개 인경우
                    answer+=map.get(num1*2);
                    map.replace(num1*2,0);
                }

                for(int j=i+1;j<numbers.size();j++){//다른 수를 반복문을 통해 찾는다
                    Long num2 = numbers.get(j);

                    if(num2==0){//그 수가 0이라면(ArrayList 상으로 정렬 X기 때문)
                        if(map.get(num1)>1){
                            answer+=map.get(num1);
                            map.replace(num1, 0);
                        }
                    }
                    else{//양쪽다 0이 아닌 경우
                        if(map.containsKey(num1+num2)){
                            answer+=map.get(num1+num2);
                            map.replace(num1+num2, 0);
                        }
                    }
                }
            }
        }

        System.out.println(answer);
    }
}

---

결과