사실상 이번 문제가 처음으로 시간 초과를 맛보는 문제가 아닐까 싶습니다. 이전 문제들은 아예 틀리거나, 성공하거나 둘 중 하나였으니까요.
시간 초과가 발생했을 경우 가장 먼저 확인해야 할 사항은 입력값의 최대 숫자입니다. 이 문제에서는 백만 개라고 했으니, O(n) 또는 O(nlogn) 시간 복잡도로 문제를 풀지 않으면 시간 초과가 발생합니다. 따라서 앞의 코드는 O(n2) 정도의 시간 복잡도가 발생했다는 의미이기도 합니다. 코드를 자세히 살펴보면 겹치는 두 쌍을 제거하고 합치는데, 만약 전체 문자열에서 제거할 문자열의 쌍이 딱 하나밖에 없었을 경우 1,000,000개→ 999,998개 → 999,996개…처럼 되어 50만 개 × 100만 개만큼 연산이 필요하기 때문에 단순 계산만으로도 가볍게 1억을 넘깁니다.
더구나 그 외에도 O(n) 연산이 많이 발생했기 때문에 실질적으로는 7만 개 이상3의 데이터는 처리하지 못하고 시간 초과가 발생합니다. 100만 개 중에서 7만 개밖에 안 됐는데 시간 초과가 발생하면 온갖 꼼수를 적용해서 최적화한다고 해도 일정 부분 이상 개선하는 것은 현실적으로 불가능합니다. 결국 이 코드는 사용하지 못하겠네요(극적으로 모든 정확성 테스트 케이스를 통과했더라도 효율성에서 반드시 실패합니다).
이럴 때는 늘 그렇듯이 생각을 바꾸어 문제를 보는 것이 중요합니다. 주어진 전체 문자열에서 알파벳 쌍을 제거하는 것보다는 순차적으로 입력받으면서 알파벳 쌍이 만들어지면 해당 부분을 먼저 제거하는 방식으로 접근해보는 겁니다. 전체 리스트에서 삭제하는 것과 순차적으로 값을 받아서 삭제하는 것 모두 결국 똑같이 전체를 탐색하는 논리이므로 충분히 가능한 방법입니다.
이렇게 순차적으로 탐색하면서 데이터를 쌓고 빼는 구현 방식을 ‘스택(stack)’이라고 하며, 앞으로 나올 문제에 종종 사용될 자료 구조이므로 나중에 라이브러리로 대체해 사용하더라도 기본 원리는 잘 기억합시다(스택은 11장에서 설명합니다).