시뮬레이션보다 불변조건을 찾아야 한다

오랜만에 투포인터 문제를 풀어보았다. LeetCode 2337.Move Pieces to Obtain a String 문제였는데, 오랜만에 알고리즘을 풀어보아서 그런지 40분이 지나도록 해결하지 못했다. 결국 AI를 통해 해설을 확인하게 되었다. 해설을 보면서 가장 인상 깊었던 점은 내 사고 과정과 풀이의 관점이 완전히 달랐다는 것이다. 나는 문제를 풀 때 머릿속으로 말을 하나씩 움직여 보며 '과정'을 시뮬레이션했다. 반면 해설은 '과정'이 아니라 문제의 불변조건(invariant)에 집중했다. 예를 들어 다음과 같은 상황을 생각해보자.

start = _L_RL__
target = _L__RL_

나는 R 이 실제로 오른쪽으로 이동할 수 있는지부터 고민했다. R의 오른쪽에는 L이 있기 때문에 당장 이동할 수 없다고 생각했고, 이 부분에서 계속 막혔다.\n 하지만 풀이에서는 현재 이동 가능 여부를 따지지 않았다. 대신 다음과 같은 불변조건을 확인했다.

• L과 R의 상대적인 순서는 절대 바뀌지 않는다.
• R은 왼쪽으로 이동할 수 없으므로 start의 R 인덱스는 target의 R 인덱스보다 작거나 같아야 한다.
• L은 오른쪽으로 이동할 수 없으므로 start의 L 인덱스는 target의 L 인덱스보다 크거나 같아야 한다.

즉, 실제로 어떻게 움직이는지를 시뮬레이션하지 않고, 모든 말이 이 불변조건을 만족하는지만 검사한다. 모든 조건을 통과하면 결국 start를 target으로 만들 수 있다는 결론에 도달한다. 이번 문제를 통해 내가 가장 크게 배운 점은 사람은 자연스럽게 '과정'을 떠올리지만, 알고리즘은 '불변조건'과 '결과'를 먼저 생각하는 경우가 많다는 것이다. 앞으로 비슷한 문제를 만나면 '어떻게 움직일까?' 보다 '절대로 변하지 않는 조건은 무엇일까?' 를 먼저 고민해 보려고 한다.

"이번 문제는 정답 하나를 배운 것이 아니라, 문제를 바라보는 관점 하나를 배웠다."