오늘 한 내용 Data Structure. Segment Tree LeetCode 2213. Longest Substring of One Repeating Character StackDay. 책임 분리와 타입 분리 배운 내용 StackDay 통계 계산 HabitStatistics를 구현하면서 계산 결과를 표현하는 타입과 계산 로직을 분리했다. 다만 HabitStatisticsCalculator가 HabitStreakCalculator에 의존하게 되면서, 여러 Calculator가 같은 날짜 정규화와 완료 기록 필터링을 반복하는 문제가 보였다. 타입을 나누는 것만으로 항상 구조가 좋아지는 것은 아니고, 공유하는 계산 맥락까지 함께 살펴봐야 한다는 점을 배웠다. 자세한 고민은 StackDay 개발일지에 정리했다. ...
문제 https://leetcode.com/problems/longest-substring-of-one-repeating-character 풀이 스트링 s에 대해 여러 번의 문자 변경 쿼리가 주어진다. 각 쿼리마다 특정 인덱스의 문자를 변경하고, 같은 문자가 연속되는 가장 긴 부분 스트링의 길이를 리턴하면 된다. 스트링의 길이와 쿼리의 개수가 최대 $10^5$이므로, 문자를 변경할 때마다 스트링 전체를 탐색하는 방식으로는 해결할 수 없다. 문자 하나를 변경하는 업데이트가 반복되고, 변경 이후 스트링 전체에서 가장 긴 연속 스트링의 길이를 구해야 한다. 따라서 변경된 구간만 갱신할 수 있는 Segment Tree를 사용했다. 다만, 단순히 concat을 하면 안되고, 두 접합부의 경계를 확인한 다음 처리를 해줘야 한다. ...
Segment Tree 배열의 특정 구간에 대한 연산을 빠르게 처리하기 위한 이진 트리 형태의 자료구조. 구간 합, 최솟값, 최댓값처럼 배열의 일정 범위를 대상으로 반복해서 연산해야 하는 경우에 사용할 수 있다. 일반적인 배열에서 특정 구간의 합을 구하려면 해당 구간의 원소를 직접 순회해야 하므로 $O(n)$의 시간이 필요하다. 세그먼트 트리는 배열의 여러 구간에 대한 연산 결과를 트리 형태로 저장하여 구간 조회를 $O(\log n)$에 처리할 수 있도록 한다. 특히 배열의 값이 변경되는 상황에서도 구간에 대한 연산을 반복해서 수행해야 할 때 사용할 수 있다. ...