백준 1253번 <좋다>

백준 알고리즘 1253번

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

1253번: 좋다

---

1253번

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

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

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

---

문제 해결

처음에는 이분탐색을 이용해 풀려고 했는데 0때문에 고려해야 할 경우가 많아져서 다른 방법으로 풀 수 있는 방법은 없을까 고민했다.

좋은 수인지 확인하려는 수를 number[idx]라고 하고, number 배열을 돌면서 number[i]와 짝이 있는지를 이분 탐색으로 찾았다.

즉, number[idx] - number[i]의 값이 number 배열에 있는지 확인하는 것을 이분 탐색으로 진행하였다. 만약 number[i]와 number[idx] - number[i]의 값이 같다면, key에 원소를, value에 개수를 저장한 HashMap에서 value를 확인해 2 이상인 경우는 좋은 수라고 우선적으로 판단했다.

이때, 문제점은 number[idx], number[i], number[idx] - number[i]가 3개 모두 0인 경우와, 3개 중 2개가 0인 경우와 같이 0이 포함되는 경우를 잘 찾지 못한다는 문제점이 있었다.

이분탐색을 하지 않고 HashMap을 사용하여 풀 수 있을 것 같다는 생각이 들었다.

HashMap은 key에 원소를, value에 해당 원소의 개수를 저장하고 좋은 수인지 확인하는 방법으로 아래와 같은 로직을 사용하였다.

좋은 수인지 확인하려는 수를 number[idx]라고 하고, number 배열을 돌 때의 반복문 변수를 i라고 하자.

• 만약 idx와 i가 같다면 넘어간다. 좋은 수인지 확인하려는 수를 가지고 덧셈을 진행하면 안되기 때문이다.
• 만약 number[idx] = number[i] = number[idx] - number[i] 라면 3개 모두 0인 경우이다. 이때 좋은 수가 되기 위해서는 number 배열에 0이 최소 3개는 있어야 한다.
• 만약 number[idx] = number[idx] - number[i] 거나 number[i] = number[idx] - number[i] 라면, 2개가 같은 경우이기 때문에 좋은 수가 되기 위해서는 해당 값이 number 배열에 최소 2개는 있어야 한다.
• 그렇지 않은 경우에는 number[idx] - number[i]의 값이 number 배열에 최소 1개가 있다면 좋은 수가 된다. (number[idx]와 number[i]는 이미 number 배열에 존재하기 때문에 number[idx] - number[i] 가 존재함을 확인하면 된다.)

---

코드

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

public class BOJ_1253 {
    static int N;
    static int[] number;
    static HashMap<Integer, Integer> map;   // key : 숫자, value : 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String[] inArr = br.readLine().split(" ");
        map = new HashMap<>();
        number = new int[N];
        for (int i = 0; i < N; i++) {
            number[i]  = Integer.parseInt(inArr[i]);
            map.put(number[i], map.getOrDefault(number[i], 0) + 1);
        }
        Arrays.sort(number);

        int answer = 0;
        for (int i = 0; i < N; i++) {
            if (isGood(i)) {
                answer++;
            }
        }
        System.out.println(answer);
    }

    // idx번 숫자가 좋은 숫자인가?
    static boolean isGood(int idx) {
        for (int i = 0; i < N; i++) {
            // 지금 확인해야 할 숫자로 덧셈을 하면 안됨
            if (idx == i) continue;
            int num = number[idx] - number[i];
            int get = map.getOrDefault(num, 0);
            if (num == number[idx] && num == number[i]) {
                if (get >= 3) return true;
            } else if (num == number[idx] || num == number[i]) {
                if (get >= 2) return true;
            } else {
                if (get > 0) return true;
            }
        }
        return false;
    }
}

---

결과

---

 

4
-10 -8 -1 -2
1

7
-10 -4 3 -1 8 4 3
4

3
1 1 1
0

5
2 2 4 6 7
2

1
1
0

2
1 2
0


3
0 0 0
3

3
0 0 1
0

3
1000000000 0 -1000000000
1