파트너 매칭

남성과 여성의 매력도 배열에서 차이가 1 이하인 쌍의 최대 개수를 구합니다. 두 배열을 정렬한 후 포인터를 이동하며 매칭합니다.

#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int maleArr[100], femaleArr[100];
    int n, m, cnt = 0, i = 0, j = 0;
    sort(maleArr, maleArr + n);
    sort(femaleArr, femaleArr + m);
    
    while (i < n && j < m) {
        int diff = abs(maleArr[i] - femaleArr[j]);
        if (diff <= 1) {
            cnt++;
            i++;
            j++;
        } 
        else if (maleArr[i] < femaleArr[j]) i++;
        else j++;
    }
    return cnt;
}

소 야구

3점조(X,Y,Z)에서 Y-X 거리와 Z-Y 거리가 [D, 2D] 범위를 만족하는 경우의 수를 계산합니다. 정렬 후 이중 포인터로 유효 구간을 탐색합니다.

#include <algorithm>
#include <cstdio>
using namespace std;

int main() {
    int positions[1010], size;
    scanf("%d", &size);
    for (int idx = 0; idx < size; idx++) scanf("%d", &positions[idx]);
    sort(positions, positions + size);

    int total = 0;
    for (int x = 0; x < size - 2; x++) {
        for (int y = x + 1, left = y + 1, right = y + 1; y < size - 1; y++) {
            int dist = positions[y] - positions[x];
            while (left < size && positions[left] - positions[y] < dist) left++;
            while (right < size && positions[right] - positions[y] <= 2 * dist) right++;
            total += right - left;
        }
    }
    printf("%d\n", total);
    return 0;
}

최장 중복 부분 수열

배열에서 중복 없이 최장 연속 부분 수열의 길이를 찾습니다. 슬라이딩 윈도우와 빈도 배열을 활용합니다.

#include <iostream>
using namespace std;

const int MAX = 100010;
int freq[MAX], seq[MAX];

int main() {
    int len, maxLen = 0;
    cin >> len;
    for (int idx = 0; idx < len; idx++) cin >> seq[idx];

    for (int right = 0, left = 0; right < len; right++) {
        freq[seq[right]]++;
        while (freq[seq[right]] > 1) {
            freq[seq[left]]--;
            left++;
        }
        maxLen = max(maxLen, right - left + 1);
    }
    cout << maxLen;
    return 0;
}

배열 요소 목표 합

두 정렬된 배열에서 요소 쌍의 합이 목표값이 되는 위치를 찾습니다. 한 배열은 시작부터, 다른 배열은 끝부터 포인터를 이동합니다.

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

int main() {
    int arrA[100010], arrB[100010];
    int n, m, target;
    cin >> n >> m >> target;
    for (int i = 0; i < n; i++) cin >> arrA[i];
    for (int i = 0; i < m; i++) cin >> arrB[i];

    for (int i = 0, j = m - 1; i < n; i++) {
        while (j >= 0 && arrA[i] + arrB[j] > target) j--;
        if (arrA[i] + arrB[j] == target) {
            cout << i << " " << j;
            break;
        }
    }
    return 0;
}

부분 수열 판별

배열 A가 배열 B의 부분 수열인지 확인합니다. B를 순회하며 A의 요소를 차례로 매칭합니다.

#include <cstdio>
int main() {
    int a[100010], b[100010], n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < m; i++) scanf("%d", &b[i]);

    int idxA = 0, idxB = 0;
    while (idxA < n && idxB < m) {
        if (a[idxA] == b[idxB]) idxA++;
        idxB++;
    }
    if (idxA == n) printf("Yes");
    else printf("No");
    return 0;
}

로그 통계

고정 시간 창 내에서 K번 이상 등장한 ID를 찾습니다. 시간 순 정렬 후 슬라이딩 윈도우로 빈도를 관리합니다.

#include <cstdio>
#include <algorithm>
using namespace std;

struct Log { int time, id; } logs[100010];
int count[100010];
bool active[100010];

int main() {
    int n, win, k;
    scanf("%d%d%d", &n, &win, &k);
    for (int i = 0; i < n; i++) scanf("%d%d", &logs[i].time, &logs[i].id);
    sort(logs, logs + n);

    for (int right = 0, left = 0; right < n; right++) {
        int id = logs[right].id;
        count[id]++;
        while (logs[right].time - logs[left].time >= win) {
            count[logs[left].id]--;
            left++;
        }
        if (count[id] >= k) active[id] = true;
    }
    for (int id = 0; id <= 100000; id++) 
        if (active[id]) printf("%d\n", id);
    return 0;
}

최장 연속 부분 수열

최대 K개의 서로 다른 숫자를 포함하는 연속 부분 수열의 최대 길이를 찾습니다. 가변 윈도우 기법을 적용합니다.

#include <iostream>
using namespace std;
const int MAX = 1000010;

int main() {
    int arr[MAX], freq[MAX], n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    int maxStart = 1, maxEnd = 1, distinct = 0;
    for (int right = 1, left = 1; right <= n; right++) {
        if (freq[arr[right]] == 0) distinct++;
        freq[arr[right]]++;
        
        while (distinct > k) {
            if (freq[arr[left]] == 1) distinct--;
            freq[arr[left]]--;
            left++;
        }
        
        if (right - left + 1 > maxEnd - maxStart + 1) {
            maxStart = left;
            maxEnd = right;
        }
    }
    cout << maxStart << " " << maxEnd;
    return 0;
}

최대 부분 행렬

두 배열에서 부분 배열 곱이 주어진 값 이하인 최대 면적을 구합니다. 부분 합과 투 포인터를 결합합니다.

#include <iostream>
#include <climits>
using namespace std;
const int SIZE = 2005;

int main() {
    int n, m, x;
    int prefix1[SIZE] = {0}, prefix2[SIZE] = {0};
    int minSum1[SIZE], minSum2[SIZE];
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> x;
        prefix1[i] = prefix1[i-1] + x;
    }
    for (int i = 1; i <= m; i++) {
        cin >> x;
        prefix2[i] = prefix2[i-1] + x;
    }

    fill(minSum1, minSum1 + SIZE, INT_MAX);
    fill(minSum2, minSum2 + SIZE, INT_MAX);
    
    for (int len = 1; len <= n; len++) {
        for (int start = 1; start + len - 1 <= n; start++) {
            int end = start + len - 1;
            minSum1[len] = min(minSum1[len], prefix1[end] - prefix1[start-1]);
        }
    }
    for (int len = 1; len <= m; len++) {
        for (int start = 1; start + len - 1 <= m; start++) {
            int end = start + len - 1;
            minSum2[len] = min(minSum2[len], prefix2[end] - prefix2[start-1]);
        }
    }

    int maxArea = 0, limit;
    cin >> limit;
    for (int i = 1, j = m; i <= n; i++) {
        while (j >= 1 && (long)minSum1[i] * minSum2[j] > limit) j--;
        maxArea = max(maxArea, i * j);
    }
    cout << maxArea;
    return 0;
}

날씨 예보

이진 문자열에서 0이 a개 이상, 1이 b개 이상인 연속 부분 문자열의 개수를 셉니다. 조건 만족 시 포인터를 이용해 효율적으로 계산합니다.

#include <iostream>
using namespace std;

int main() {
    int n, a, b;
    string s;
    cin >> n >> a >> b >> s;
    s = " " + s;
    long cntZero = 0, cntOne = 0, total = 0;

    for (int left = 1, right = 0; left <= n; left++) {
        while (right < n && (cntZero < a || cntOne < b)) {
            right++;
            if (s[right] == '0') cntZero++;
            else cntOne++;
        }
        if (cntZero >= a && cntOne >= b) {
            total += n - right + 1;
        }
        if (s[left] == '0') cntZero--;
        else cntOne--;
    }
    cout << total;
    return 0;
}