투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다.
알고리즘이 매우 간단하므로 바로 문제로 들어가보자.

2018번

아이디어

• 연속된 숫자이기 때문에 start_index와 end_index가 같은 값으로 시작한다.

수도 코드

N (연속된 자연수의 합)

start_index = 1

end_index = 1

sum = 1

while(end_index != N):

	if(sum == N):
    
    	경우의 수 증가
        
        end_index 증가
        
        sum 값 변경 ( end_index 증가 후에 변경해야함 )
    	
    else if(sum > N):
    
    	sum 값 변경 ( start_index 증가 전에 변경해야함 )
        
        start_index 증가
    
    else if(sum < N):
    
    	end_index 증가
        
        sum 값 변경 ( end_index 증가 후에 변경해야함 )

경우의 수 출력

답안

#include <iostream>
using namespace std;

int N;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> N;
  int start_index = 1;
  int end_index = 1;
  int count = 1;
  int S = 1;
  while (end_index != N) {
    if (S == N) {
      count++;
      S -= start_index;
      start_index++;
    } else if (S > N) {
      S -= start_index;
      start_index++;
    } else {
      end_index++;
      S += end_index;
    }
  }
  cout << count << "\n";
}

1940번

아이디어

• 연속된 숫자가 아니기 때문에 start_index와 end_index가 떨어진 채로 시작한다.

수도 코드

N (재료의 개수), M (갑옷이 되는 번호)

A (재료 데이터 저장 배열)

for(N만큼 반복):

	재료 배열 저장
    
재료 배열 정렬

start_index = 0

end_index = 배열 마지막 인덱스

while(i < j):

	if(재료 합 < M): start_index를 증가
    
    else if(재료 합 > M): end_index를 감소
    
    else if(재료 합 == M):
    
    	count++
   
   		start_index++
        
        end_index--
   
count 출력

답안

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

int N; // 재료의 개수
int M; // 합친 번호
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);cout.tie(NULL);
  cin >> N >> M;
  vector<int> A;
  for(int i = 0; i < N; i++){
    int temp;
    cin >> temp;
    A.push_back(temp);
  }
  sort(A.begin(), A.end());
  int start_index = 0;
  int end_index = A.size() - 1;
  int count = 0;
  while(start_index < end_index){
    if(A[start_index] + A[end_index] == M){
      count++;
      start_index++;
      end_index--;
    }
    else if(A[start_index] + A[end_index] < M){
      start_index++;
    }
    else if(A[start_index] + A[end_index] > M){
      end_index--;
    }
  }
  cout << count << "\n";
  
}

1253번⭐

아이디어

• 좋은 수 하나를 찾는데 시간 복잡도가 O(N제곱)이라면 최종 시간 복잡도는 O(N세제곱) 이다.
  따라서 좋은 수 하나를 찾는데 사용되는 시간 복잡도는 O(nlogn) 이하여야 한다.
  O(nlongn) 에는 정렬, 투포인터가 사용된다.

수도 코드

N (배열의 데이터 개수)

A (데이터 저장 배열)

for(N만큼 반복):
	
    배열 A에 데이터 저장
    
배열 A 정렬

count = 0 // 정답

for(k-> 0이상 N미만): // A[k] = 찾고자 하는 값
    
    start_index = 0
    
    end_index = N-1
    
	while(start_index < end_index):
    	
        if(start_index == k):
        
        	start_index++
            
            continue
        
        else if(end_index == k):
        
        	end_index--
            
            continue
            
        if(A[start_index] + A[end_index] == A[k]):
        
        	count++ 
            
        	break
            
        else if(A[start_index] + A[end_index] < A[k]):
        
        	start_index++
            
        else if(A[start_index] + A[end_index] > A[k]):
        
        	end_index--
    	
count 출력

답안

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

int N, cnt;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> N;
  vector<long long> A(N, 0);
  for (int i = 0; i < N; i++)
    cin >> A[i];

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

  for (int k = 0; k < N; k++) {
    int start_index = 0;
    int end_index = N - 1;
    while (start_index < end_index) {
      if (start_index == k) {
        start_index++;
        continue;
      }
      if (end_index == k) {
        end_index--;
        continue;
      }
      if (A[start_index] + A[end_index] == A[k]) {
        cnt++;
        break;
      } else if (A[start_index] + A[end_index] < A[k])
        start_index++;
      else
        end_index--;
    }
  }
  cout << cnt << "\n";
}