정렬 기반 패턴

Source: Dev.to

개요

정렬 기반 패턴은 데이터를 먼저 정렬한 뒤, 정렬된 순서를 활용해 로직을 단순화하거나 복잡성을 줄이거나, 두 포인터 혹은 탐욕적 결정과 같은 효율적인 패턴을 적용할 수 있게 합니다. 정렬은 복잡한 문제를 구조화된 문제로 변환하는 경우가 많습니다.

사용 시점

다음 상황에서 이 패턴을 사용하세요:

• 요소들의 순서가 중요할 때
• 상대적인 비교가 중요할 때
• 그룹화 혹은 짝짓기가 필요할 때
• 두 포인터나 탐욕적 로직을 적용하고 싶을 때
• 작은 시간 증가(정렬)로 큰 단순화를 얻을 수 있을 때

시간 및 공간

• 정렬 시간: O(N log N)
• 후처리: 보통 O(N)
• 공간 복잡도: 정렬 구현에 따라 O(1) 또는 O(N)

핵심 아이디어

• 배열을 먼저 정렬한다
• 정렬된 특성을 이용해:
  • 불필요한 비교를 제거한다
  • 단조로운 결정을 내린다
  • 패턴을 쉽게 감지한다
  • 정렬 후 선형 스캔이나 포인터 기반 기법을 적용한다

예시 1: 정렬을 이용한 Two Sum

문제: 목표값과 합이 되는 쌍이 존재하는지 확인한다.

로직:

1. 배열을 정렬한다.
2. 양 끝에서 시작하는 두 포인터를 사용한다.

def two_sum_sort(nums, target):
    nums.sort()
    left = 0
    right = len(nums) - 1

    while left  0 and nums[i] == nums[i - 1]:
            continue

        left = i + 1
        right = len(nums) - 1

        while left  2:
                return False

    return True

식별 체크리스트

다음 질문을 해보세요:

• 정렬된 순서가 결정을 단순화시키나요?
• 정렬을 통해 선형 스캔이 가능해지나요?
• 상대적인 순서가 중요한가요?
• N log N 정도의 복잡도가 허용 가능한가요?

위 질문에 모두 ‘예’라면 정렬 기반 패턴이 적합합니다.

흔히 저지르는 실수

• 정렬 후 중복 요소 처리를 놓치는 경우
• 안정적인 정렬이 필요 없는데 가정하는 경우
• 원본 순서를 유지해야 하는데 정렬을 수행하는 경우
• 더 빠른 비정렬 솔루션을 간과하는 경우

요약

• 먼저 정렬하고, 나중에 생각한다.
• 두 포인터와 탐욕 전략을 가능하게 한다.
• 복잡도 감소의 핵심이 되는 경우가 많다.
• 반드시 알아야 할 기본적인 문제 해결 패턴이다.