[BOJ 1253] '좋은' 투 포인터

2개의 포인터 이동 규칙을 알아두자

 

 

백준 1253. ‘좋은 수’ 구하기
(시간 제한 2초)

 

 

< 문제 >

주어진 N개의 수 중에서 다른 두 수의 합으로 표현되는 수가 있다면 그 수를 ‘좋은 수’라고 한다.

N개의 수 중 좋은 수는 총 몇 개인지 출력하시오.

 

 

< 입력 >

1번째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 2번째 줄에는 N개의 수의 값(Ai)이 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)

 

 

< 출력 >

// 예제 입력
10
1 2 3 4 5 6 7 8 9 10

// 예제 출력
8

 

 

< 풀이 >

 

시간 복잡도

for문으로 배열을 모두 돌며 ‘좋은 수’를 모두 찾으려면 O(n)의 시간 복잡도가 필요하다.

‘좋은 수’ 하나를 찾는 알고리즘의 시간 복잡도는 O(n^2)보다 작아야 한다.

만약 O(n^2)보다 크다면, 최종 시간 복잡도는 O(n^3)이 되어 제한 시간을 초과한다.

(N을 최대값인 2,000이라고 가정하면, 2,000^3 = 8,000,000,000이므로
제한 시간 2초 동안 가능한 연산 횟수 200,000,000을 초과한다.)

 

따라서 ‘좋은 수’ 하나를 찾는 알고리즘의 시간 복잡도는 최소 O(n log(n))이어야 한다.

배열의 수를 정렬한 후, 투 포인터 알고리즘을 사용하면 된다.

 

 

주의할 점

1. 같은 두 수를 합해서는 안 된다.
2. 자기 자신을 ‘좋은 수’ 만들기에 포함시켜서는 안 된다.

 

 

풀이 과정

1. 입력받은 수를 배열 arr에 저장한 후 오름차순으로 정렬한다.
2. 판별의 대상이 되는 수를 0부터 k까지 반복한다.
3. 투 포인터 i, j를 배열의 양 끝에 위치시켜 초기화한다.
4. 투 포인터 이동 원칙에 따라 i가 j보다 커지기 전까지 포인터를 이동시킨다.
   1. 합이 arr[k]보다 작으면 → i 증가
   2. 합이 arr[k]보다 크면 → j 감소
   3. 합이 arr[k]일 때
      1. i와 j가 둘 다 k가 아니면 (주의할 점 1번 위반) → count 증가, while문 탈출
      2. i가 k라면 (주의할 점 2번 위반) → i 증가
      3. j가 k라면 (주의할 점 2번 위반) → j 감소
5. count를 출력한다.

 

 

코드

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

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());
        Long[] arr = new Long[N];

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");

        for (int i = 0; i < N; i++) {
            arr[i] = Long.valueOf(st.nextToken());
        }
        Arrays.sort(arr);

        int count = 0;

        for (int k = 0; k < N; k++) {
            int i = 0;
            int j = N - 1;

            while (i < j) {
                if (arr[i] + arr[j] < arr[k]) {
                    i++;
                } else if (arr[i] + arr[j] > arr[k]) {
                    j--;
                } else {
                    if (i != k && j != k) {
                        count++;
                        break;
                    } else if (i == k) {
                        i++;
                    } else {
                        j--;
                    }
                }
            }
        }
        System.out.println(count);
    }
}