[JAVA]BOJ 3273, 두 수의 합

 

<문제 분석>

n: 수열의 크기, n의 크기 만큼 입력받음 (1 <= n <= 1000000)

a[ ]: 입력받는 배열

x: ' a[i] + a[j] = x ' 에서의 x

 

2가지 방법이 떠올랐다.

1. a[n] 에 입력받고, 하나하나 x - a[i] 의 값이 a[n] 에 있는지 확인한다. 이중 for문 사용-> O(n^2)

2. count sort 사용, 1000000 칸의 배열을 만들고 입력받은 n의 값을 증가시킨다. 그리고 a[i]와 a[x - i]가 둘 다 1인지 확인한다. -> 1000000번 을 두 번 돌면 되므로 O(n)

 

시간복잡도 때문에 1번은 안된다.. 그러므로 2번 선택

 

import java.io.*;
import java.util.StringTokenizer;

public class BOJ3273 {
    // count sort
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n, x, i, result = 0;
        String str;
        StringTokenizer st;

        n = Integer.parseInt(bf.readLine());

        int[] cArr = new int[1000001];

        // count sort 배열 만들기
        str = bf.readLine();
        st = new StringTokenizer(str);
        for(i=0;i<n;i++){
            cArr[Integer.parseInt(st.nextToken())]++;
        }

        x = Integer.parseInt(bf.readLine());

        for(i=1;i<1000001;i++){
//            if((cArr[i] == 1) && (x - i > 0) && (x - i) < 1000001) // x - i의 범위가 중요
//                if(cArr[x - i] == 1)
//                    result++;

			//위와 같은 코드
            if((x - i > 0) && (x - i) < 1000001)
                result += ((cArr[i] == 1) && (cArr[x - i] == 1)) ? 1 : 0;
        }
        // 중복 없이 세는 코드
//        for(i = 1; i<=(x-1)/2;i++){
//            if(x - i <= 1000000)
//                result += ((cArr[i] == 1) && (cArr[x - i] == 1)) ? 1 : 0;
//        bw.write(result + "");
//        bw.flush();

//        if(result % 2 == 1) // 짝홀 구분 필요 x
//            bw.write(result / 2 + 1 + "");
//        else
        bw.write(result / 2 + "");
        bw.flush();
    }
}

 

처음에는 x - i의 범위를 생각하지 못해서  arrayIndexOutOfBounds 에러가 났다. 만약 x = 13 이고 i가 100(a[i])이라면 너무나도 당연히 x가 되는 짝꿍 숫자(a[j])가 없을텐데... x - i는 cArr[1000001] 에 대한 인덱스 값이므로 0 < x - i < 1000001 라는 조건이 필요하다. 안그러면 나처럼 에러난다.

 

또 놓친점.. a[i] + a[j] = x 인데, i와 j는 i < j , 그리고 쌍이라는 조건이 있으므로 3 + 3 = 6 이런 것은 불가능하다. 제외하고 경우의수를 세어야 한다.

 

첫 for문은 전체를 다 확인하므로(1000000번) 중복해서 결과를 센다. 그러므로 출력시 /2 를 해야한다. 만약 3 + 3 = 6 처럼 쌍이아닌 합이 있는 경우는 홀수값이 되므로 /2를 했을때 올바른 결과가 나온다. 굳이 더 코드를 작성할 필요가 없다..

 

처음부터 중복을 세지 않는 방법도 있다. for문에서 범위가 i<=(x - 1)/2 인 경우이다. -1 을 한 이유는 3 + 3 = 6 과 같은 나 자신으로만 이뤄진 합을 세지 않으려고 했기때문이다. 똑같은 O(n)이지만 1000000번을 늘 돌지 않으니 조금 더 빠를것 같다.