[백준 Java] 1253 좋다

🔗 문제링크 🔗

1253번: 좋다

---

🌟  1번 풀이   ❯❯  해시를 이용한 풀이 🌟

그냥 해시만 이용해도 풀리긴 한다 (꽤나 비효율적인 방법으로)

해당 방법에서 체크할 포인트는 0인경우에 대한 반례 체크이다.

0 0 0과 같은 경우 '0' 3개가 모두 만들어질 수 있다. (더해도 값을 유지한다) 

 

🍳 코드(시간이 더 오래 걸리는 코드) 🍳

package 백준.hash;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class boj_1253_좋다2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        HashSet<Integer> hash = new HashSet<>();

        int[] arr = new int[n];
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            hashMap.put(arr[i], hashMap.getOrDefault(arr[i], 0) + 1); // 입력되는 각 숫자의 개수를 센다.
        }

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int sum = arr[i] + arr[j];

                if (arr[i] == 0 && arr[j] == 0) {
                    if (hashMap.getOrDefault(sum, 0) >= 3) { //둘다 0인 경우는 3개 인상인 경우에만 가능
                        hash.add(sum);
                    }
                } else if (arr[i] == 0 || arr[j] == 0) {
                    if (hashMap.getOrDefault(sum, 0) >= 2) { //둘 중 하나만 0인경우에는 0이 2개 이상인 경우에만 가능
                        hash.add(sum);
                    }

                } else {
                    hash.add(sum); //계산한 합
                }

            }
        }

        int cnt = 0;
        for (int num : arr) {
            if (hash.contains(num)) cnt++; //계산된 합이 숫자 중에 있다면 더한다.
        }
        System.out.println(cnt);


    }
}

---

🌟  2번 풀이 ❯❯  정렬을 통해 투 포인터 방식을 사용한 풀이 🌟

시간 복잡도를 줄이는 방법 더하는 경우 이기 때문에 

정렬된 경우 현재 숫자가 나오는 방법을 찾는 방법이다 ( 현재 arr [left] + arr [right]가 arr [nowIdx] 보다 크면 left를 한 칸 오른쪽 이동하고  작으면 right를 한 칸 왼쪽으로 이동한다. 이는 정렬된 상태 이기 때문에 큰 경우에는 더 작은 값을 취하고 작은 경우에는 더 큰 값을 취하는 것이다.)  

여기서 체크해야할 문제는 숫자에 음수가 나올 수 있다는 것이다. -2 0 1 2와 같은 경우 숫자 '0'은 '-2' + '2'를 통해서 만들어질 수 있다.

즉 투 포인터를 처음과 끝을 이용해야 한다. 하지만 이 경우에 -2 0 1 2 와 같은 경우 '2'는 '0'+'2'로만 나올 수 있지만 문제 조건상 자신을 포함해서는 안된다. 즉 이경우에도 '0'을 체크하거나 자신을 제외하고 계산해 주어야 한다. (left 나 right가 nowIdx인 경우 반드시 이동하도록 구현하였다)

🍳 코드(투포인터 풀이) 🍳

package 백준.binarySearch;

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

public class boj_1253_좋다 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int start = 0;
            int end = n - 1;

            while (start < end) {
                if (start == i || end == i) { //본인 이라면
                    if (start == i) start++;
                    else end--;
                } else {
                    int now = arr[start] + arr[end];
                    if (arr[i] == now) { //찾은 경우 
                        cnt++;
                        break;
                    } else if (now < arr[i]) { // 더 큰 숫자가 필요한 경우
                        start++;
                    } else { // 더 작은 숫자가 필요한 경우
                        end--;
                    }
                }
            }
        }

        System.out.println(cnt);
    }
}