투 포인터라는 개념을 처음 접했을 때는 저는 이것을 단지 pointer 2개를 사용해서 문제를 해결하는 것이라고 착각했었습니다.
하지만 투 포인터는 포인터 2개를 이용해서 한번의 반복에서 2개의 포인터를 움직이는 것만으로 내가 원하는 정답을 구하는 것이었습니다.
백준 2018번 문제를 풀어보면서 투 포인터의 개념을 잡을 수 있었습니다.
문제
자연수 N을 입력 받았을 때 해당 값을 연속 된 다른 자연수의 합으로 나타낼 수 있는 경우의 수를 구하는 문제입니다.
해결 방법
저는 처음에 i, e의 2개의 포인터를 이용해서 1부터 시작해서 천천히 모든 경우를 확인하면 된다고 생각했었습니다. 그렇게 해서 자바와 c++일 경우에는 알고리즘 문제를 해결할 수 있었습니다.
- C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int e;
int cnt = 1;
for (int i = 1; i <= n/2; i++) {
e = i+1;
int sum = i;
while(sum <= n) {
sum += e;
if (sum == n) cnt++;
e++;
}
}
cout << cnt;
return 0;
}- Java
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int cnt = 1;
for (int i = 1; i <= n/2; i++) {
int e = i + 1;
int sum = i;
while (sum <= n) {
if (sum == n) cnt++;
sum += e;
e++;
}
}
bw.write(cnt + "\n");
bw.flush();
bw.close();
}
}하지만 파이썬의 경우는 시간초과가 계속해서 발생했습니다. 이후 확인해보니 파이썬의 경우는 c++이나 java보다 처리 속도가 느린 것이 그 이유였습니다. 또한 제가 문제를 해결한 방식이 사실 2 포인터가 아니었다는 것을 여기서 알게 되었습니다.
진짜 2포인터는 한 번의 반복 내에서 sum 값을 초기화 시키는 것이 아니라 2개의 포인터의 위치를 조정하면서 sum 값을 조정해야 하는 것이었습니다.
그렇게 해서 구현화 코드는 다음과 같습니다.
- 파이썬
import sys
input = sys.stdin.readline
print = sys.stdout.write
n = int(input())
cnt = 1
start, end = 1, 1
sum_val = 1
while end < n:
if (sum_val == n):
cnt += 1
end += 1
sum_val += end
elif (sum_val < n):
end += 1
sum_val += end
else:
sum_val -= start
start += 1
print(str(cnt))위의 2방식과 다른 점은 위의 방식은 시작 포인터의 값이 커질 때마다 sum과 end 포인터를 초기화시켜 사실상 완전 탐색과 속도면에서 크게 다를 바가 없었습니다.
하지만 아래의 파이썬으로 구현한 코드는 sum 값을 유지한 채로 포인터의 위치만을 한번의 반복에 변화시켜 O(n)의 속도로 알고리즘을 완성할 수 있었습니다.
덕분에 파이썬에서도 알고리즘을 통과할 수 있었습니다.
