[1253] 좋다

✔ 좋다

[백준 1253]

문제 분석하기

N의 개수가 최대 2000이므로 좋은 수 하나를 찾는 알고리즘의 시간 복잡도는 N² 보다 작지 않을 경우

최종 시간 복잡도가 N³(8000000000 > 200000000)이 되어 제한 시간 안에 문제를 풀 수 없게 됨

그러므로 데이터를 정렬하고 자기 자신을 포함하지 않도록 투 포인터를 지정하여 문제에 접근

손으로 풀어보기

1. 수를 입력받아 배열에 저장한 후 정렬
2. 투 포인터 i, j를 양쪽 끝에 위치시킨 후 조건에 적합한 포인터 이동 원칙을 활용해 탐색을 수행
   • A[i] + A[j] > K: j--; 
   • A[i] + A[j] < K: i++;
   • A[i] + A[j] == K: i++; j++; count++;
3. 배열의 모든 수에 대하여 반복

슈도코드 작성하기

N(수의 개수)
A(수 데이터 저장 배열)
for(N만큼 반복하기) {
    A 배열에 데이터 저장하기
}
A 배열 정렬하기
for(k를 0부터 N까지 반복) {
    변수 초기화하기(찾고자 하는 값 find, 포인터 i, 포인터 j)
    while(i < j) {
        if(A[i] + A[j] == 찾고자 하는 값)
            두 포인터 i, j가 k가 아닐 때 결괏값에 반영 및 while문 종료하기
            두 포인터 i, j가 k가 맞을 때 포인터 변경 및 계속 수행하기
        else if(A[i] + A[j] < 찾고자 하는 값) 포인터 i 증가
        else 포인터 j 감소
    }
}
좋은 수의 개수 출력하기

코드 구현하기

/**
 * 1253) 좋다
 */
public class D008_1253 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // N(수의 개수)
        int N = Integer.parseInt(br.readLine());
        int Result = 0;
        // A(수 데이터 저장 배열)
        long A[] = new long[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        // A 배열에 데이터 저장하기
        for (int i = 0; i < N; i++) {
            A[i] = Long.parseLong(st.nextToken());
        }
        // A 배열 정렬하기
        Arrays.sort(A);
        for (int k = 0; k < N; k++) {
            // 찾고자 하는 값 find
            long find = A[k];
            // 투 포인터
            int i = 0;
            int j = N - 1;
            while (i < j) {
                if (A[i] + A[j] == find) {
                    // 두 포인터 i, j가 k가 아닐 때만 결괏값에 반영 및 while문 종료하기
                    if (i != k && j != k) {
                        Result++;
                        break;
                    } else if (i == k) {
                        i++;
                    } else if (j == k) {
                        j--;
                    }
                } else if (A[i] + A[j] < find) {
                    i++;
                } else {
                    j--;
                }
            }
        }
        System.out.println(Result);
        br.close();
    }
}