백준 3273번 - 두 수의 합

이중 for문을 통해 모든 경우를 체크할 수도 있겠지만, 그렇게 풀 경우 시간초과가 날 것입니다. 문제에서 주어지는 수열은 모두 서로 다른 양의 정수라는 점을 이용하여 모든 수를 정렬 후 , 두 개의 포인터를 사용하여 더 간단하게 풀어보겠습니다.

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

public class Boj3273 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int x = Integer.parseInt(br.readLine());
        int answer = 0;
        Arrays.sort(arr); // 오름차순 정렬
        int i = 0, j = n - 1;
        while (i < j) {
            if (arr[i] + arr[j] < x) {
                i++;
            } else if (arr[i] + arr[j] > x) {
                j--;
            } else {
                answer++;
                i++;
                j--;
            }
        }
        System.out.println(answer);
    }
}

 

 

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

 

입력받은 값을 배열에 저장해준 뒤, Arrays.sort() 메서드를 이용해 오름차순으로 정렬해줍니다. 그럼 맨 앞은 가장 작은 수 , 맨 뒤는 가장 큰 수가 올 것입니다. 

이제 포인터 i,j 두 개를 설정할건데, 하나는 가장 작은 값을 가리키고 다른 하나는 가장 큰 값을 가리키면서 시작하겠습니다.

만약 arr[i]와 arr[j]의 합이 x보다 작다면, x가 되기위해서는 더 큰 값이 필요할 것입니다. 따라서 i의 값을 1 증가시켜줍니다. 비슷하게 arr[i]와 arr[j]의 합이 x보다 크다면 이 말은 더하는 수를 작게 조정해야한다는 것입니다. 따라서 j의 값을 1 감소시켜줍니다. 만약 두 수의 합이 x라면 문제의 조건을 만족하는 쌍이므로 answer의 값을 증가시키고, i와 j의 값도 한 칸씩 옮겨줍니다. 그러다가 i<j 라는 조건이 false가 되면, 가능한 모든 쌍을 구한 것이므로 while문을 빠져나오고 답을 구할 수 있습니다.