백준 3273 자바 - 두 수의 합 (BOJ 3273 JAVA)

문제 : https://www.acmicpc.net/problem/3273

 

  보통 풀고보면 풀이 방법이 비슷비슷한 경우가 많은데, 아무래도 입력값 n이 10만개 밖에 안되다보니 재밌게도 풀이방법이 매우 다양한 문제이다.

 

일단, 단순히 2중 반복문으로 모든 쌍을 더해보면 O(N^2)이므로 시간초과다. 그럼 그 외에 시간 내에 가능한 풀이법에 대해 보자.

 

  일반적으로 사람들이 많이 사용한 풀이 방법은 2가지 정도 있었다.

1. 정렬 후, 모든 값을 확인하며 x-a_i가 존재하는지 이분탐색으로 확인 : 정렬 O(NlogN) + N개에 대한 이분탐색 O(NlogN)

2. 정렬 후, 투 포인터 알고리즘으로 맨앞과 맨뒤에서 시작한 포인터를 움직이며 더해봄 : 정렬 O(NlogN) + 탐색 O(N)

 

---

 

  내 경우엔 brute force로 O(N)으로 풀었다. 이하 풀이는 a_i가 양수이고 최대 100만으로 매우 작은 수치라 가능했다. 보통 100만처럼 작은 수치로 주어지는 문제가 잘 없기 때문에 대부분 위의 두가지 방식으로 푼 것 같다.

 

  로직은 그냥 1~1000000 까지 나온 수에 대해 존재여부를 기록하고 (100만개짜리 배열 혹은 해시셋), 입력 들어온 모든 값에 대해 x-a_i 값이 위에서 기록해둔 배열 혹은 해시셋에 존재하는지만 확인하면 된다. 이 풀이의 경우 존재여부 판단에 O(N) + 탐색 O(N)이 걸린다. 최종적으로 카운팅된 값을 2로 나눈 값이 결과값이다(1+2, 2+1 이렇게 두 번 세어졌을 것이므로).

 

---

 

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/03200/BOJ_3273.java

import java.io.DataInputStream;
import java.io.IOException;

public class Main {
    private void solution() throws Exception {
        boolean[] v = new boolean[1000001];
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            int a = nextInt();
            v[arr[i] = a] = true;
        }
        int x = nextInt();

        int cnt = 0;
        for (int i = 0; i < n; i++) {
            int target = x-arr[i];
            if (target <= 0 || target > 1000000) continue;
            if (v[target]) cnt++;
        }
        System.out.println(cnt/2);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }

    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    private static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    private static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}