두 수의 합

풀이

첫번째 시도

package BOJ;

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

public class sol3273 {
    static int n;
    static int x;
    static int[] arr;
    static int count = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        x = Integer.parseInt(br.readLine());
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] + arr[j] == x) {
                    count++;
                }
            }
        }
        System.out.println(count);
    }
}

시간복잡도에 대해 한 번 더 공부하고 푼 문제라서, 위 코드처럼 이중 for문을 사용하여 풀이를 하면 시간복잡도가 O(n^2)이고 n의 최대 100,000이기 때문에 시간초과가 날 것이라고 생각했다. 역시나 제출을 하니 시간초과가 떴다.

두번째 시도

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

public class Main {
    static int n;
    static int x;
    static int[] arr;
    static int count = 0;
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        x = Integer.parseInt(br.readLine());
        visited = new boolean[2000001];
        for (int i = 0; i < n; i++) {
            if (x <= arr[i]) continue;
            if (visited[x - arr[i]]) {
                count++;
            }
            visited[arr[i]] = true;
        }
        System.out.println(count);

    }
}

바킹독 배열 강의에서 나온 것처럼 합(x)-arr[i]에 저장된 값이 visited 배열에 존재하면 쌍이 있다고 판단하고 count를 더해주고, 없으면 일단 해당 visited[arr[i]]를 true로 바꿔주는 것을 n만큼 반복하여 시간 복잡도를 O(n)으로 줄여서 풀이하였다.
여기서 주의할 점은 x가 arr[i]의 값보다 작은 경우를 continue 처리해주지 않으면 두번째 if문에서 인덱스가 음수가 되어 런타임 에러 (ArrayIndexOutOfBounds)가 발생할 수 있다는 점이다.

다른 풀이로는 투 포인터를 사용한 풀이가 있다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public int count(int N, int[] arr, int X) {
		int result = 0;
		int sum = 0;
		int lt = 0;
		int rt = N-1;
		
		Arrays.sort(arr);
		
		while(lt < rt) {
			sum = arr[rt] + arr[lt];
			
			if(sum == X) result++;
			
			if(sum < X) {
				lt++;
			}else {
				rt--;
			}
		}
		return result;
	}
	
	public static void main(String[] args) throws IOException {
		Main num = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.valueOf(st.nextToken());
		st = new StringTokenizer(br.readLine());
		
		int[] arr = new int[N];
		
		for(int i=0; i<N; i++) {
			arr[i] = Integer.valueOf(st.nextToken());
		}
		
		int X = Integer.valueOf(br.readLine());
		
		System.out.println(num.count(N, arr, X));
	}
}

배열의 양 끝 인덱스를 가리키는 두 개의 포인터를 선언 후 초기화하고 배열을 오름차순으로 정렬 후 두 포인터가 가리키는 값의 합 x와 같으면 count를 더해준다. 오름차순으로 정렬했으니 합이 x보다 작다면 오른쪽 포인터를, 크다면 왼쪽 포인터를 한칸씩 옮겨가며 확인하면 된다.