📖 투 포인터 알고리즘?
해당 알고리즘은 포인터라고 하는 두개의 변수를 사용하여 해결해야 할 문제에 따라서 다른 속도,방향으로 이동하여 문제를 해결하는 방법입니다.
특징
- 알고리즘 적용전에 요소를 정렬하거나 순서를 지정해야 합니다.
- 현재 값을 기준으로 왼쪽 또는 오른쪽 포인터를 움직이는 조건이 필요합니다.
🤔 사용해야 하는 이유는?
해당 알고리즘의 주된 장점은 두개의 포인터를 사용하여 배열,리스트와 같은 연결된 목록을 한번에 통과합니다. 때문에 불필요한 반복이나 비교를 방지하여 시간 복잡도를 줄일 수 있습니다. O(n^2) -> O(n)
목표값까지 합치는 인덱스 2개를 찾아야 하는 문제의 경우 두개의 포인터를 사용하여 배열의 양쪽 끝에서 이동하고 합이 목표값보다 크거나 작은지 확인할 수 있습니다. 이렇게 하면 중간 결과를 저장하기 위해 중첩된 루프나 불필요한 메모리를 사용하지 않아도 됩니다.
✅ 예제
[BOJ] 2018 : 수들의 합 5문제 링크
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N;
static int answer = 1;
public static void main(String[] args) throws IOException {
inputs();
solution();
output();
}
private static void solution() {
int sum = 1;
int start = 1;
int end = 1;
while (end != N) {
if (sum == N) {
++end;
++answer;
sum += end;
} else if (sum < N) {
++end;
sum += end;
} else {
sum -= start;
++start;
}
}
}
private static void output() {
System.out.println(answer);
}
private static void inputs() throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
}
}
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N, M, answer;
static int[] arr;
public static void main(String[] args) throws IOException {
inputs();
solution();
output();
br.close();
}
private static void solution() {
//1. arr배열 오름차순 정렬
//2. left=1,right=N 지정하여 목표값과 대조 하며 포인터 이동
//3. left>=right 되면 탐색완료 이므로 종료 -> 결과 출력
Arrays.sort(arr);
int left = 1;
int right = N;
while (left < right) {
int sum = arr[left] + arr[right];
if (M == sum) {
++answer;
++left;
} else if (M > sum) {
++left;
} else {
--right;
}
}
}
private static void output() {
System.out.println(answer);
}
private static void inputs() throws IOException {
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
arr = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
}
}
문제 링크
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int N;
static int[] arr;
static int answer = 0;
public static void main(String[] args) throws IOException {
inputs();
solution();
output();
br.close();
}
private static void solution() {
//1.배열 정렬
//2.맨 끝부터 idx을 정한다음 해당 타겟이 목표값이 되는 투포인터 알고리즘
//3. target이 존재하면 ++answer이후 반복문 종료
//4. left >= right가 되면 전부 탐색을 한 것이므로 반복문 종료 이후 정답 출력.
Arrays.sort(arr, 1, N + 1);
for (int idx = 1; idx <= N; idx++) {
int left = 1;
int right = N;
long target = arr[idx];
while (left < right) {
long sum = arr[left] + arr[right];
if (sum == target) {
if (left == idx) {
++left;
continue;
}
if (right == idx) {
--right;
continue;
}
++answer;
break;
} else if (sum < target) {
++left;
} else {
--right;
}
}
}
}
private static void output() {
System.out.println(answer);
}
private static void inputs() throws IOException {
N = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
arr = new int[N + 1];
for (int i = 1; i <= N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
}
}
문제 링크
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int S, P; //S : 임의로 만든 dna길이, P : 추출할 비밀번호 길이 / 1…P…S…1,000,000
static char[] DNA; // 임의로 입력 받은 dna
static int[] ACGT; // 비밀번호에 생성 요구사항 저장
static int[] state;
static int answer;
public static void main(String[] args) throws IOException {
inputs(); // 입력값 받기
solution();
output();
br.close();
}
private static void solution() {
initialSubArr(); //1. 초기 슬라이싱 배열 만들고 검사
slicingArr(); //2. 앞뒤로 한개씩만 더하고 뺀다. P>S 종료
}
private static void slicingArr() {
for (int R = P; R < S; R++) {
int L = R - P;
addDNA(DNA[R]);
removeDNA(DNA[L]);
if (isSuccess())
++answer;
}
}
private static void removeDNA(char c) {
int idx = findDNA(c);
state[idx]--;
}
private static int findDNA(char c) {
switch (c) {
case 'A':
return 0;
case 'C':
return 1;
case 'G':
return 2;
case 'T':
return 3;
}
return -1;
}
private static void initialSubArr() {
state = new int[4];
for (int i = 0; i < P; i++) {
addDNA(DNA[i]);
}
if (isSuccess()) ++answer;
}
private static boolean isSuccess() {
for (int i = 0; i < 4; i++) {
if (state[i] < ACGT[i])
return false;
}
return true;
}
private static void addDNA(char c) {
int idx = findDNA(c);
state[idx]++;
}
private static void output() {
System.out.println(answer);
}
private static void inputs() throws IOException {
st = new StringTokenizer(br.readLine());
S = Integer.parseInt(st.nextToken());
P = Integer.parseInt(st.nextToken());
DNA = br.readLine().toCharArray();
ACGT = new int[4];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 4; i++) {
ACGT[i] = Integer.parseInt(st.nextToken());
}
}
}
왜? 라는 질문이 사라질 때까지