모각코 5회차(240201)

[백준/BOJ] 1253번 좋다 (자바/Java)

 

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

1253번: 좋다

---

1. 문제

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

 

2. 풀이

처음에는 백트래킹으로 n개의 수 중에서 2개를 뽑은 후 해당 2개를 더한 값과 일치하는 수를 찾아서 count하는 방식으로 구현했다.

 

당연히 이런 문제가 골드4일리도, 정답률이 20퍼대일리도 없었다. 시간초과가 났다..

 

 

백트래킹에는 전혀 문제가 없어 보였다. 최대 2000개 중에서 2개를 뽑는 경우의 수는 O(n^2)이니까.

그래서 다른 곳에서 찾아보았다. 아마 조합 2개를 뽑아서 연산하는 과정에서 시간복잡도가 n증가하여 O(n^3)이 된 것 같다.

 

 

그래서 다른 식으로 접근했다. HashMap을 사용하였다. key로는 '좋은 수'를 넣고 values에는 좋은 수가 될 수 있는 조합을 배열을 원소로 갖는 리스트로 만들어서 넣어줬다. 메모리가 너무 클까 걱정했지만 간당하게 될 것 같아 구현한 끝에 성공했다.

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

public class Main {
    static int n;
    static int[] num;
    static boolean[] visit;
    static int count = 0;
    static Map<Integer, List<int[]>> perfectNum = new LinkedHashMap<>();
    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());
        num = new int[n];
        visit = new boolean[n];

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

        choose2Number(n ,0, new int[2], 0, new int[2]);
        
        // map 검사
        for(int i=0; i<num.length; i++){
            int j = num[i]; // j는 좋은 수
            List<int[]> ints = perfectNum.get(j); // ints는 좋은 수가 되기 위한 후보 인덱스
            if(ints == null) continue;

            boolean isContain = true;
            // isContain이 false가 되려면, 자기 자신의 인덱스가 아닌 두 수의 합으로 만들어야한다.
            for (int[] idx : ints) {
                if(idx[0] != i && idx[1] != i) {
                    isContain = false;
                    break;
                }
            }

            if(!isContain) count++;

        }

        System.out.println(count);
    }

    private static void choose2Number(int n, int x, int[] arr, int start, int[] idx) {
        if(x == arr.length){
        	// 뽑힌 두 수가 이미 map에 반영되어있다면 기존의 value에 원소를 추가하고
            // map에 반영되어있지 않다면 새로운 value를 넣어줘야한다.
            if(perfectNum.get(arr[0]+arr[1]) == null){
                LinkedList<int[]> ints = new LinkedList<>();
                ints.add(new int[]{idx[0], idx[1]});
                perfectNum.put(arr[0]+arr[1], ints);
            }else{
                List<int[]> ints = perfectNum.get(arr[0]+arr[1]);
                ints.add( new int[]{idx[0], idx[1]});
                perfectNum.put(arr[0]+arr[1], ints);
            }

            return;
        }

        for(int i=start; i<n; i++){
            arr[x] = num[i];
            idx[x] = i;
            choose2Number(n, x + 1, arr, i + 1, idx);
        }
    }
}

 

 

하지만 더 좋은 풀이는 '투 포인터'였다. n개의 수를 정렬한 후에, 이를 왼쪽 끝과 오른쪽 끝의 포인터 2개를 사용하는 것이다.

가장 먼저 for문으로 n개의 수를 돈다. 첫번째 for문이 가리키는 수가 '좋은 수'라고 가정한다.

 

이제 투포인터는 이 좋은 수를 만들기 위한 두 원소를 찾기 위한 포인터이다.

 

왼쪽과 오른쪽의 합이 만약 좋은 수보다 크다면, 오른쪽 포인터를 하나 줄여서 수를 낮춘다.

만약 두 포인터가 가르키는 수의 합이 좋은 수보다 크다면 왼쪽 포인터를 늘리는 것이다.

 

이렇게 하면 시간복잡도도, 메모리도 전혀 고려하지 않아도 그냥 넘어간다. 개미쳤다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
            nums[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(nums);  // 정렬
        int res = 0;
        for (int sumIdx = 0; sumIdx < N; sumIdx++) {
            int left = 0; int right = N-1;  // 투포인터
            while (true) {
                if (left == sumIdx) left++;
                else if (right == sumIdx) right --;

                if (left >= right) break;

                if (nums[left] + nums[right] > nums[sumIdx]) right--;
                else if (nums[left] + nums[right] < nums[sumIdx]) left++;
                else{
                    res++;
                    break;
                }
            }
        }
        System.out.println(res);
    }
}

 

3. 결과

4. 총평

 - 투포인터 알고리즘을 이해하고 효율적인 알고리즘을 찾기 위한 노력을 해야겠다.