[알고리즘/자료구조] 투 포인터 & 슬라이딩 윈도우

투 포인터 

2개의 포인터로 시간 복잡도를 최적화 하는 알고리즘!

시간복잡도 : O(N)

 

슬라이딩 윈도우

2개의 포인터로 범위를 지정한 뒤, 범위를 유지한 채로 이동하며 문제 해결! 투포인터와 매우 유사하다.
시간복잡도 : O(N)

 

 

 

투 포인터) 백준 1253번

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

#include <iostream>
#include <vector>
#include <algorithm>
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    int N;
    std::cin >> N;

    std::vector<int> vec(N, 0);
    for (int i = 0; i < N; ++i) {
        std::cin >> vec[i];
    }
    std::sort(vec.begin(), vec.end());

    int count = 0;

    for (int k = 0; k < N; ++k) {
        int i = 0;
        int j = N - 1;
        while (i < j) {
            if (vec[i] + vec[j] < vec[k]) {
                ++i;
            }
            else if (vec[i] + vec[j] > vec[k]) {
                --j;
            }
            else {
                if (i != k && j != k)
                {
                    ++count;
                    break;
                }
                else if (i == k) {
                    ++i;
                }
                else if (j == k) {
                    --j;
                }
            }
        }
    }
    std::cout << count << "\n";
}

 

슬라이딩 윈도우) 백준 12891

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

#include <iostream>
#include <vector>
#include <algorithm>

int N, P;
std::string myStr;
int checkList[4];   //{‘A’, ‘C’, ‘G’, ‘T’}
int myList[4] = {0,};

void addMyList(int i) {
    if (myStr[i] == 'A') {
        ++myList[0];
    }
    else if (myStr[i] == 'C') {
        ++myList[1];
    }
    else if (myStr[i] == 'G') {
        ++myList[2];
    }
    else if (myStr[i] == 'T') {
        ++myList[3];
    }
}
void removeMyList(int i) {
    if (myStr[i] == 'A') {
        --myList[0];
    }
    else if (myStr[i] == 'C') {
        --myList[1];
    }
    else if (myStr[i] == 'G') {
        --myList[2];
    }
    else if (myStr[i] == 'T') {
        --myList[3];
    }
}
bool checkMyList() {
    for (int i = 0; i < 4; i++) {
        if (myList[i] < checkList[i])
            return false;
    }
    return true;
}

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);

    std::cin >> N >> P;
    std::cin >> myStr;
    for (int i = 0; i < 4; ++i) {
        std::cin >> checkList[i];
    }

    int count = 0;
    for (int i = 0; i <P; ++i) {
        addMyList(i);
    } 
    if (checkMyList())
        ++count;

    for (int i = 0, j = P; j < N; ++i, ++j) {
        removeMyList(i);
        addMyList(j);
        if (checkMyList())
            ++count;
    }
    
    std::cout << count << "\n";
}