안녕하세요 이번 시간에는 투 포인터 문제 유형에 대해 분석해보는 시간을 갖도록 하겠습니다. 투 포인터 문제는 O(n) 탐색을 더 빠르게 수행할 때 주로 사용되며 맵의 원소 중 몇 개의 원소를 합쳐서 특정 값이 되는 경우의 수를 구하는 문제에서 자주 사용됩니다.
백준 2018(수들의 합5) 문제의 경우 N을 연속된 자연수의 합으로 나타낼 수 있는 가짓수를 구하는 문제입니다. 연속된 수의 합이기 때문에 시작 인덱스와 종료 인덱스를 둘 다 시작값으로 설정하여 종료 인덱스가 N이 될 때까지 탐색한다면 총합이 N과 같을 경우 정답을 1 증가시키고 N보다 클 경우 현재 더한 수 중 가장 작은 수를 빼는, 즉 시작 인덱스를 앞으로 이동시킵니다. 마찬가지고 총합이 N보다 작을 경우 다음 수를 더하는, 즉 종료 인덱스를 증가시키고 그 값을 더합니다.
백준 1940(주몽) 문제의 경우 두 개의 재료를 합쳐서 M이 되면 갑옷이 만들어질 때 몇 개의 갑옷을 만들 수 있는지를 구하는 문제입니다. 입력 배열이 불규칙하기 때문에 배열을 정렬한 후 투 포인터를 이용하여 탐색합니다. 시작 인덱스를 시작점, 종료 인덱스를 끝점으로 하여 시작 인덱스보다 종료 인덱스가 클 때까지 각 인덱스가 가리키는 배열의 값의 합이 N보다 작다면 값을 키워야 하므로 시작 인덱스를 증가, N보다 크다면 값을 줄여야 하기 때문에 종료 인덱스를 감소시키며, N이라면 카운트 한 후 양 인덱스의 차를 줄이는 방식으로 탐색합니다.
백준 1253(좋다) 문제의 경우 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있는 좋은 수의 개수를 구하는 문제입니다. 마찬가지로 입력 배열이 불규칙하기 때문에 배열을 정렬한 후 투 포인터를 이용하여 탐색하며, N개의 수를 하나씩 탐색하면서 현재 수보다 작은 수 범위에서 투 포인터 탐색을 진행합니다. 시작 인덱스는 시작점, 종료 인덱스를 끝점으로 하여 시작 인덱스보다 종료 인덱스가 클 때까지 두 인덱스가 가리키는 배열값의 합이 k보다 작으면 값을 키워줘야 하기 때문에 시작 인덱스를 증가시키며, k보다 크다면 값을 줄여줘야 하기 때문에 종료 인덱스를 감소시킵니다. 여기서 합이 k와 같다면 서로 다른 두 수의 합 여부를 확인하기 위해 시작 인덱스와 종료 인덱스가 모두 k가 아니라면 정답에 추가, 시작 인덱스가 k라면 시작 인덱스를 증가시키고 종료 인덱스가 k라면 종료 인덱스를 감소시킵니다. 여기서 주의할 점은 배열을 정렬하기 때문에 인덱스를 0부터 입력받아야 한다는 점입니다. 그렇지 않다면 가장 작은 수가 0번 인덱스에 들어가서 잘못된 결과를 출력합니다.
