[백준/C] 3273번 두 수의 합 (더블포인터)

https://www.acmicpc.net/problem/3273

3273번: 두 수의 합

 

풀이 검색해서 풀었다.

1. 오름차순으로 퀵 정렬부터 먼저 한 후
2. 더블 포인터 이용 (배열 왼쪽 끝/오른쪽 끝)

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX_STRING_SIZE 100001

void swap(int arr[], int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

int partition(int arr[], int left, int right) {
    int pivot = arr[left], low = left + 1, high = right, temp;
    while (low <= high) {
        while (low <= right && pivot >= arr[low]) low++;
        while (high >= (left + 1) && pivot <= arr[high]) high--;
        if (low <= high) swap(arr, low, high);
    }
    swap(arr, left, high);
    return high;
}

void quickSort(int arr[], int left, int right) {
    if (left <= right) {
        int pivot = partition(arr, left, right);
        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }
}

void check(int arr[], int left, int right, int x) {
    int cnt = 0;
    while (1) {
        if (left >= right)
            break;
        int sum = arr[left] + arr[right];
        if (sum == x) {
            cnt++;
            left++;
            right--;
        }
        else if (sum < x)
            left++;
        else
            right--;
    }
    printf("%d", cnt);
}

int main() {
    int n, x, i, k; // n: 정수 개수
    int a[MAX_STRING_SIZE];

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    quickSort(a, 0, n - 1); // 퀵 정렬

    scanf("%d", &x);
    check(a, 0, n - 1, x);
}

 

---

시간초과된 코드

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#define MAX_STRING_SIZE 100001

int main() {
    int n, x, i, k, cnt = 0; // n: 정수 개수
    int a[MAX_STRING_SIZE];

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d", &x);

    i = 0;
    k = n - 1;

    while(1) {
        if (a[i] + a[k] != x) { // x와 다르면
            k--;

            if (i == k-1) { // i에 대응하는 k 모두 검토했으면
                i++;
                k = n - 1;
            }
        }
        else {
            i++;
            k = n - 1;
            cnt++;
        }

        if (i == k-1) break;

    }
    printf("%d", cnt);
}