두 포인터 구현 바로잡기 ★

책 "알고리즘 산책"에서 다음과 같은 내용을 보았다.

...하지만 재귀 호출을 완전히 없애서 함수 호출에 따르는 오버헤드를 피해 보자.
정의 2.1 모든 형식 매개변수를 각각에 상응하는 인자로 사용하는 꼬리 재귀 호출을 순 꼬리 재귀 호출(strictly tail-recursive)이라고 한다.
재귀 호출을 하기 전에 변수의 값을 미리 설정해 주면 순 꼬리 재귀 호출로 고칠 수 있다.

int mult_acc3(int r, int n, int a) {
    if (odd(n)) {
        r = r+a;
        if (n == 1) return r;
    }
    n = half(n);
    a = a+a;
    return mult_acc3(r,n,a);
}​

이제 꼬리 재귀 호출을 while(true) 구문으로 바꾸기만 하면 손쉽게 반복문 형태의 프로그램으로 고칠 수 있다.

int mult_acc3(int r, int n, int a) {
    while (true) {
        if (odd(n)) {
            r = r+a;
            if (n == 1) return r;
        }
        n = half(n);
        a = a+a;
    }
    return mult_acc3(r,n,a);
}​

 

이를 보고 느낀 것이 있다.
두 포인터 구현에서, while(true) 직후의 반복문 최상단 상태에서 모든 변수가 순 꼬리 재귀 값을 가져야 반복문 내부에서 항상 직관적이고, 가독성 높은 코드를 작성할 수 있다는 것이다.

예를 들어, 필자는 전에 2018을 다음과 같은 방식으로 풀었다:

while (1) {
    if (sum == n) result++;
    if (sum >= n) sum -= s++;
    else if (e <= n) sum += e++;
    else break;
}

가독성이 낮고, 이 글을 쓰면서 디버깅에 애를 먹었다.
하지만, 다음과 같이 새로이 코드를 작성했다:

while (e <= n) {
    if (sum == n) r++;
    if (sum >= n) sum -= s++;
    else sum += ++e;
}

이 코드는 반복문 상단에서 sum의 값이 $[s,e]$의 구간합을 나타낸다.
반면 앞선 구현은 sum이 $[s,e+1]$의 구간합을 나타냈기 때문에 마지막 2개의 구문이 복잡해졌다.

같은 방식으로 WA×4, CE×1을 받은 뒤에 AC를 받은 4158번의 코드를 보자:

for (int i = 0, j = 0; i < n and j < m;) {
    if (a[i] > b[j]) {
        ++j;
    } else if (a[i] < b[j]) {
        ++i;
    } else {
        ++cnt;
        ++i;
    }
}

사실 줄바꿈을 하지 않아서 틀린 거다.
하지만, 이와 별개로 코딩 스타일을 획일화 해보자.

while (x < n and y < m) {
    if (a[x] == b[y]) ++cnt;
    if (a[x] <= b[y]) ++x;
    else ++y;
}

확실히 깔끔하다.
참고로, 이 while문의 조건에는 x와 y에 대한 조건이 모두 있다. 그 이유는 각 포인터가 이동하는 위치가 다르기 때문이다.

다음은 3273번을 살펴보자. 한번에 AC를 받기는 했지만, 코드를 더 깔끔하고 가독성이 높게 줄여보았다:

while (s < e) {
    if (sum == x) ++cnt;
    if (sum > x) sum += -arr[e]+arr[--e];
    else sum += -arr[s]+arr[++s];
}

다음은 2470번 문제이다. 다른 이유로 WA×1을 받았지만, 깔끔하게 고쳤다.

while (s < e) {
    if (abs(sol[s]+sol[e]) < mn) {
        mn = abs(sol[s]+sol[e]);
        ans = {s, e};
    }
    if (sol[s]+sol[e] <= 0) ++s;
    else --e;
}

다음은 1806 문제이다.
WA×6을 받고나서야 AC를 받았다. 원래 코드 형태는 이루 말 못할 정도로 처참하기에 싣지 않는다. 아무튼 다음과 같이 깔끔하게 고칠 수 있다:

while (e < n) {
    if (sum >= S) ans = min(ans, e-s+1);
    if (sum >= S) sum -= arr[s++];
    else sum += arr[++e];
}

마지막으로 7453번 문제이다:

while (x < n and y < m) {
    ll sum = a[x] + b[y];
    if (sum == 0) {
        ll l = 0, r = 0;
        do l++, x++; while (x < n and a[x] == a[x - 1]);
        do r++, y++; while (y < m and b[y] == b[y - 1]);
        answer += l * r;
    }
    else if (sum > 0) y++;
    else x++;
}

앞서 살짝 얘기했지만, 확실히 구분해보겠다.
두 포인터를 순회하는 구조는 크게 3가지로 구분된다.

• 1개의 배열 위에 2개의 포인터가 있는 경우
  • 포인터가 같은 방향으로 이동(1)
  • 포인터가 마주보며 이동(2)
• 2개의 배열에 각각 1개의 포인터가 있는 경우
  • 포인터가 같은 방향으로 이동(3)

위 분류에 따라,
while의 조건문 내부에
(1)의 경우 e < n 또는 e <= n가,
(2)의 경우 s < e 또는 s <= e가,
(3)의 경우 x < n and y < m 또는 x <= n and y <= m가
들어간다는 것을 확인했다.

아 맞다.
두 포인터 탐색 과정에서 해가 되는지 확인하고 어떤 작업을 수행하는 과정은 상단에 적는 것이 좋다.
왜냐하면 포인터의 이동이 발생하면 이상한 값이 있기 때문이다.

-끝-