[C++] 투 포인터(Two Pointer)

투 포인터(Two Pointer)

1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작하여 원하는 값을 얻는 알고리즘이다.

 

투 포인터

 

문제

 

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

2003번: 수들의 합 2

#include <iostream>
using namespace std;

int arr[10000];

int main()
{
	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int ans = 0, sum = 0;
	int start = 0, end = 0;
	while (1) {
		if (sum >= M)
			sum -= arr[start++];
		else if (end == N)
			break;
		else
			sum += arr[end++];

		if (sum == M)
			ans++;
	}
	cout << ans;
}

 

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

1806번: 부분합

#include <iostream>
using namespace std;

int arr[100000];

int main()
{
	int N, S;
	cin >> N >> S;
	for (int i = 0; i < N; i++)
		cin >> arr[i];

	int ans = -1;
	long long sum = 0;
	int start = 0, end = 0;
	while (1) {
		if (sum >= S)
			sum -= arr[start++];
		else if (end == N)
			break;
		else
			sum += arr[end++];

		if (sum >= S && (ans == -1 || end - start < ans))
			ans = end - start;
	}
	if (ans == -1)
		cout << 0;
	else
		cout << ans;
}

 

https://leetcode.com/problems/container-with-most-water/

Container With Most Water - LeetCode

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

class Solution {
public:
    int maxArea(vector<int>& height) {
        int start = 0, end = height.size() - 1;
        int answer = (end - start) * min(height[start], height[end]);
        while (start < end) {
            if (height[start] <= height[end])
                start++;
            else
                end--;

            answer = max(answer, (end - start) * min(height[start], height[end]));
        }

        return answer;
    }
};

 

https://leetcode.com/problems/3sum/

3Sum - LeetCode

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

class Solution
{
public:
    vector<vector<int>> threeSum(vector<int> nums)
    {
        vector<vector<int>> answers;
        int target;

        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (target == -nums[i])
                continue;

            target = -nums[i];
            int left = i + 1, right = nums.size() - 1, sum = 0;
            while (left < right)
            {
                sum = nums[left] + nums[right];

                if (target > sum)
                    ++left;
                else if (target < sum)
                    --right;
                else
                {
                    vector<int> temp = {nums[left], -target, nums[right]};
                    answers.push_back(temp);

                    while (left < nums.size() && nums[left] == temp[0])
                        ++left;
                    while (right >= 0 && nums[right] == temp[2])
                        --right;
                }
            }
        }

        return answers;
    }
};

 

https://leetcode.com/problems/3sum-closest/

3Sum Closest - LeetCode

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

class Solution
{
public:
    int threeSumClosest(vector<int>& nums, int target)
    {
        int closest = 1e9, num1 = 1e9;

        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); ++i)
        {
            if (num1 == nums[i])
                continue;

            num1 = nums[i];
            int num2 = i + 1, num3 = nums.size() - 1, sum = 0;
            while (num2 < num3)
            {
                sum = num1 + nums[num2] + nums[num3];

                int diff1 = abs(sum - target);
                int diff2 = abs(closest);
                closest = diff1 < diff2 ? sum - target : closest;

                if (sum < target)
                    ++num2;
                else if (sum > target)
                    --num3;
                else
                {
                    vector<int> temp = { nums[num2], nums[num3] };
                    while (num2 < nums.size() && nums[num2] == temp[0])
                        ++num2;
                    while (num3 >= 0 && nums[num3] == temp[1])
                        --num3;
                }
            }
        }

        return target + closest;
    }
};

 

슬라이딩 윈도우(Sliding Window)

투 포인터처럼 구간을 훑으면서 지나간다는 공통점이 있으나 어느 순간에도 구간의 넓이가 동일하다는 차이점이 있다.

 

슬라이딩 윈도우

 

문제

 

https://programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

#include <string>
#include <vector>
using namespace std;

int StringToSec(string s)
{
	int time = stoi(s.substr(0, 2)) * 3600;
	time += stoi(s.substr(3, 2)) * 60;
	time += stoi(s.substr(6, 2));

	return time;
}

string SecToString(int i)
{
	string time = "";

	int s = i % 60;
	i /= 60;

	int m = i % 60;
	i /= 60;

	int h = i;

	if (h < 10)
		time += "0";
	time += to_string(h) + ":";

	if (m < 10)
		time += "0";
	time += to_string(m) + ":";

	if (s < 10)
		time += "0";
	time += to_string(s);

	return time;
}

int total_time[360000]{};

string solution(string play_time, string adv_time, vector<string> logs) {
	int play_time_sec = StringToSec(play_time);
	int adv_time_sec = StringToSec(adv_time);

	if (play_time_sec == adv_time_sec)
		return SecToString(0);

	for (int i = 0; i < logs.size(); ++i) {
		int start = StringToSec(logs[i].substr(0, 8));
		int end = StringToSec(logs[i].substr(9, 8));

		for (int i = start; i < end; i++)
			total_time[i]++;
	}

	int ans = 0, start = 0, end = adv_time_sec;
	long long sum = 0, max = 0;
	for (int i = start; i < end; i++)
		sum += total_time[i];
	max = sum;

	while (end <= play_time_sec) {
		int diff = -total_time[start++] + total_time[++end - 1];
		sum += (long long)diff;

		if (sum > max) {
			max = sum;
			ans = start;
		}
	}

	return SecToString(ans);
}

 

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

2531번: 회전 초밥

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

int sushi[300001];
int sushi_kind[3001];

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

    int N, D, K, C;
    cin >> N >> D >> K >> C;
    for (int i = 0; i < N; i++)     
        cin >> sushi[i];

    int cnt = 0;
    int result = 0;

    // 1~K 까지의 초밥을 덱에 넣고 종류를 센다.
    deque<int> dq;
    for (int i = 0; i < K; i++) {
        dq.push_back(sushi[i]);
        if (!sushi_kind[sushi[i]]++)
            cnt++;
        result = max(result, cnt);
    }

    for (int i = 0; i < N - 1; i++) {
        // 맨 앞 스시를 빼고 해당 스시의 종류가 덱에 없을 경우 cnt를 뺀다.
        dq.pop_front();
        if (!(--sushi_kind[sushi[i]]))
            cnt--;

        // 다음 스시를 덱에 넣고 새로운 종류라면 cnt를 더해준다
        dq.push_back(sushi[(i + K) % N]);
        if (!(sushi_kind[sushi[(i + K) % N]])++)
            cnt++;

        result = max(result, cnt + (sushi_kind[C] == 0));
    }

    cout << result;
}

 

거북이와 토끼(Tortoise and Hare)

https://fierycoding.tistory.com/45

플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise & Hare Algorithm) / 증명 / leetcode 287번 / 파이썬

 

문제

https://leetcode.com/problems/linked-list-cycle/description/

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == nullptr)
            return false;
        
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next && fast->next->next)
        {
            fast = fast->next->next;
            slow = slow->next;

            if(fast == slow)
            return true;
        }
        return false;        
    }
};

 

https://leetcode.com/problems/reorder-list/description/

#include <stack>

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head; // mid
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        stack<ListNode*> st;
        while (slow != nullptr) {
            st.push(slow);
            slow = slow->next;
        }

        ListNode* node = head;
        while(!st.empty()) {
            ListNode* temp = st.top();
            st.pop();

            temp->next = node->next;
            node->next = temp;
            node = temp->next;
        }
        node->next = nullptr;
    }
};