[Algorithm]🐿️99클럽 코테 스터디 10일차 TIL : 백준 1253 좋다

🔍문제

https://www.acmicpc.net/problem/1253
N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다.
N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라.
수의 위치가 다르면 값이 같아도 다른 수이다.

🤔발상

두 수의 합을 구하는 문제는 정렬된 배열일 경우, 양 끝에 포인터 지정하고, 포인터를 움직이면서 원하는 값보다 큰지 작은지를 판단하면서 포인터를 이동하는 투 포인터 알고리즘으로 해결할 수 있습니다.

🔦입출력

N의 수는 2천개이며, N의 값은 10억이므로 두 수의 합은 INT 범위 이내고 투포인터로 탐색할 때 오래걸리지 않는 수입니다. O(N)

📃의사코드

    1. 숫자들을 오름차순으로 정렬한다.
    2. 각 수마다 투포인터로 해당 수를 만들 수 있는지 확인
    3. 만들 수 있다면 카운트를 증가시킨다.

👨‍💻코드

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

public class Main {
    public static void main(String[] args) throws IOException{
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
            int n = Integer.parseInt(br.readLine());
            int[] arr = new int[n];
            Arrays.sort(arr);

            String[] sarr = br.readLine().split(" ");
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(sarr[i]);
            }


            int count = 0;
            for (int i = 0; i < n; i++) {
                int start = 0;
                int end = n - 1;
                while (start < end) {
                    if (start == i) {
                        start++;
                        continue;
                    }
                    if (end == i) {
                        end--;
                        continue;
                    }
                    int sum = arr[start] + arr[end];
                    if (sum == arr[i]) {
                        count++;
                        break;
                    } else if (sum < arr[i]) {
                        start++;
                    } else {
                        end--;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

🚀TIL

• - 투포인터 알고리즘을 알고있다면 쉽게 해결할 수 있는 문제입니다.
• 삼중 포인터 문제도 예전에 리트코드에서 풀어본 기억이 있는데, 재귀형식으로 포인터 하나를 고정한 뒤에, 다시 자신을 호출하여 2가지 변수를 선택하는 알고리즘이었습니다. 복습을 해두면 좋을 것 같습니다.