알고리즘 최적화로 성능 1850% 향상, 이진수 처리와 시간 범위 충돌 해결 전략

Context

이진 문자열을 최대 홀수 값으로 재배치하는 효율적 알고리즘 설계 필요. 자정 전후를 포함한 두 시간 범위 간의 비어 있지 않은 교집합(Conflict) 판별 로직 구현 요구.

Technical Solution

• 최대 홀수 이진수 생성을 위해 최상위 비트에 1을 배치하고 최하위 비트에 1을 고정하는 전략 채택
• 정렬(O(n log n)) 대신 1과 0의 개수를 직접 세어 문자열을 생성하는 Counting 방식 도입으로 시간 복잡도 최적화
• 시간 문자열을 분 단위 정수로 변환하여 연산 효율성을 높이는 전처리 과정 수행
• 모듈로(Modulo) 연산을 통해 자정을 넘어가는 시간 범위의 지속 시간을 계산하고 시작점을 음수로 보정하는 범위 정규화 설계
• 두 범위의 끝점이 상대 범위의 시작점보다 크고 시작점이 상대 범위의 끝점보다 작은 조건으로 겹침 여부를 판별하는 인터섹션 로직 적용

Impact

• Counting 방식 적용 시 Sorting 방식 대비 성능 1850% 향상(2,500,000/s)
• Splitting 방식 대비 성능 1300% 향상(2,500,000/s)

Key Takeaway

• 단순 정렬보다 데이터의 특성(이진수)을 활용한 카운팅 방식이 시간 복잡도와 실제 처리량에서 압도적인 효율을 제공함. 시간 범위 판별 시 도메인 특성(자정)을 고려한 정규화 과정이 로직의 단순화와 정확성을 결정함.