[백준/C++] 1940 - 주몽

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

처음 작성한 코드는 아래와 같다.

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    int nums[n];
    for (int i = 0; i < n; i++)
        cin >> nums[i];

    int count = 0;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] == m) count++;
        }
    }

    cout << count << endl;

    return 0;
}

다만 이렇게 하면 이중 for문을 사용함으로써 시간복잡도가 O(N^2)가 되기 때문에 코드를 개선해 보았다.
vector 배열을 사용하였고,
양끝을 가리키는 변수를 사용하기 위해 입력받은 nums를 sort를 통해 오름차순 정렬해주었다. (sort 함수 사용법: 인자로 시작주소, 끝주소를 각각 넣어주면 된다.)

이후 left가 right보다 작은 동안 왼쪽+오른쪽 합을 sum에 저장하고,
sum이 m과 같다면 count 1 증가, 양끝을 하나씩 이동
sum이 m보다 작다면 왼쪽 끝만 1 증가
sum이 m보다 크다면 오른쪽 끝만 1 증가
시키는 방식으로 진행한다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> nums(n);
    for (int i = 0; i < n; i++)
        cin >> nums[i];

    sort(nums.begin(), nums.end());

    int left = 0, right = n - 1;
    int count = 0;

    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == m) {
            count++;
            left++;
            right--;
        }
        else if (sum < m) left++;
        else right--;
    }

    cout << count << endl;
    return 0;
}

제출해보니 실제로 시간이 엄청 줄어든 것을 확인할 수 있었다!