시간/공간 복잡도 자동 분석

[devchanki]

목표

DaleStudy 알고리즘 PR에 각 솔루션 파일의 시간/공간 복잡도를 자동 분석하여 댓글로 제공한다.

요구사항

입력 파일

PR의 Files Changed로 들어오는 솔루션들은 아래와 같이 각 폴더 내의 솔루션이 포함되는 형태다.

• container-with-most-water (directory)
  • tedkimdev.rs
• valid-parenthesses (directory)
  • tedkimdev.rs

솔루션 파일 형식

// TC: O(n)
// SC: O(1)
impl Solution {
    pub fn max_area(heights: Vec<i32>) -> i32 {
        let (mut left, mut right) = (0, heights.len() - 1);
        let mut res = 0i32;
        while left <= right {
            res = res.max(((right - left) as i32) * heights[left].min(heights[right]));

            if heights[right] < heights[left] {
                right -= 1;
            } else {
                left += 1;
            }
        }

        res
    }
}

• 상단의 TC, SC는 있을수도 없을 수도 있고 특정 주석 입력 형식이 있는 것이 아니다.
• 솔루션 파일은 정해진 확장자가 아니라 여러가지 확장자가 될 수 있다. (py, js 등)
• 하나의 솔루션 파일에 여러 가지 풀이가 포함될 수 있다. (예: 같은 문제를 brute force, 최적화 등 다양한 접근으로 풀어 하나의 파일에 작성)

R1. 복잡도 자동 계산

• 트리거: PR opened / reopened / synchronize
• 대상: 솔루션 파일 (기존 SOLUTION_PATH_REGEX 재사용)
• 출력: 파일별 review comment (subject_type: "file")
  • 시간복잡도 (Big-O)
  • 공간복잡도 (Big-O)
  • 1-2줄 근거
• 멀티 솔루션: 파일 내 풀이가 여러 개인 경우 각 풀이를 개별 분석

R2. 기존 주석 검증

• 주석 포맷: 자유 포맷 허용 (언어별 주석 스타일 자동 인식)
  • 예시: // TC: O(n), # 시간복잡도: O(n log n), /* Space: O(1) */ 등
  • 정해진 포맷 없이 유연하게 파싱
• 주석이 있는 경우:
  • 유저 분석값과 실제 계산값을 테이블로 비교
  • 일치 시 ✅, 불일치 시 ❌ 표시
  • 불일치 시 다시 풀어보는 것을 권장하는 톤으로 피드백
• 주석이 없는 경우: R1만 실행 (계산값만 제공) + 주석 작성 권장 안내
• 멀티 솔루션: 각 풀이 바로 위의 주석을 해당 풀이의 유저 분석으로 매핑

R3. 개선 제안

• 의미 있는 개선 여지(최소 한 단계 이상, 예: O(n²) → O(n))만 제안
• 문제 제약조건을 모를 수 있으므로 "고려해볼 만한 대안" 톤 유지
• 현재 구현이 적절하면 "현재 구현이 적절해 보입니다" 명시

댓글 본문 포맷 (Output Format)

R1/R2/R3을 하나의 댓글에 통합하여 아래 포맷으로 작성한다.

단일 풀이 케이스

케이스 1: 유저 주석 있음 + 일치

<!-- dalestudy-complexity-analysis -->
### 📊 시간/공간 복잡도 분석

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n) | O(n) | ✅ |
| **Space** | O(1) | O(1) | ✅ |

**피드백**: 정확합니다! 배열을 한 번 순회(O(n))하며 상수 공간만 사용하는 최적의 풀이입니다.

케이스 2: 유저 주석 있음 + 불일치

<!-- dalestudy-complexity-analysis -->
### 📊 시간/공간 복잡도 분석

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n) | O(n log n) | ❌ |
| **Space** | O(1) | O(n) | ❌ |

**피드백**: sort()를 사용하고 있어 시간 복잡도는 O(n log n)이며, 정렬 과정에서 O(n) 추가 공간이 필요합니다. 한번 다시 분석해보시는 것을 권장드립니다!

케이스 3: 유저 주석 없음 (복잡도 분석만 제공)

<!-- dalestudy-complexity-analysis -->
### 📊 시간/공간 복잡도 분석

| | 복잡도 |
|---|---|
| **Time** | O(n) |
| **Space** | O(1) |

**피드백**: 배열을 한 번 순회하며 최솟값과 최대 이익을 갱신하는 방식입니다.

> 💡 풀이에 시간/공간 복잡도를 주석으로 남겨보세요!

멀티 풀이 케이스

하나의 솔루션 파일에 여러 풀이가 포함된 경우, <details> 접기를 활용하여 댓글 길이를 관리한다.

• 풀이가 1개: 기존 포맷 그대로 (접기 없음)
• 풀이가 2개 이상: 각 풀이를 <details>로 감싸고, summary에 결과(✅/❌)를 표시하여 접힌 상태에서도 핵심 정보를 확인할 수 있도록 한다.
• 풀이 식별: 함수명 + 접근 방식 설명으로 각 풀이를 구분한다.
• 주석 매핑: 각 함수 바로 위의 주석을 해당 풀이의 유저 분석으로 매핑한다.

케이스 4: 멀티 풀이 (유저 주석 있음)

<!-- dalestudy-complexity-analysis -->
### 📊 시간/공간 복잡도 분석

> ℹ️ 이 파일에는 **3가지 풀이**가 포함되어 있어 각각 분석합니다.

<details>
<summary>풀이 1: <code>findMin_use_math_min</code> — Time: ❌ O(n⁴) → O(n) / Space: ✅ O(n)</summary>

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n⁴) | O(n) | ❌ |
| **Space** | O(n) | O(n) | ✅ |

**피드백**: Math.min(...nums)는 spread 연산자로 인자를 펼치므로 O(n) 시간이며, 콜스택에 O(n) 공간이 필요합니다. 한번 다시 분석해보시는 것을 권장드립니다!

</details>

<details>
<summary>풀이 2: <code>findMin_naive</code> — Time: ❌ O(n³) → O(n) / Space: ✅ O(1)</summary>

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n³) | O(n) | ❌ |
| **Space** | O(1) | O(1) | ✅ |

**피드백**: 배열을 한 번 순회하는 단순 탐색이므로 시간복잡도는 O(n)입니다. 한번 다시 분석해보시는 것을 권장드립니다!

</details>

<details>
<summary>풀이 3: <code>findMin</code> — Time: ❌ O(n log n) → O(log n) / Space: ✅ O(1)</summary>

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n log n) | O(log n) | ❌ |
| **Space** | O(1) | O(1) | ✅ |

**피드백**: 이진 탐색으로 탐색 범위를 절반씩 줄이므로 O(log n)입니다. 한번 다시 분석해보시는 것을 권장드립니다!

</details>

케이스 5: 멀티 풀이 (유저 주석 없음)

<!-- dalestudy-complexity-analysis -->
### 📊 시간/공간 복잡도 분석

> ℹ️ 이 파일에는 **2가지 풀이**가 포함되어 있어 각각 분석합니다.

<details>
<summary>풀이 1: <code>twoSum_bruteForce</code> — Time: O(n²) / Space: O(1)</summary>

| | 복잡도 |
|---|---|
| **Time** | O(n²) |
| **Space** | O(1) |

**피드백**: 이중 루프로 모든 쌍을 탐색하는 brute force 방식입니다.

</details>

<details>
<summary>풀이 2: <code>twoSum</code> — Time: O(n) / Space: O(n)</summary>

| | 복잡도 |
|---|---|
| **Time** | O(n) |
| **Space** | O(n) |

**피드백**: HashMap을 활용하여 한 번의 순회로 해결하는 최적 풀이입니다.

</details>

> 💡 풀이에 시간/공간 복잡도를 주석으로 남겨보세요!

PR 통합 댓글 (최종 포맷)

하나의 PR에 포함되어 있는 각 솔루션들에 대해서 하나의 댓글로 위의 내용들을 작성한다. 각 솔루션 파일이 단일 풀이인지 멀티 풀이인지에 따라 위의 해당 케이스 포맷을 적용한다.

<!-- dalestudy-complexity-analysis -->
### 📊 시간/공간 복잡도 분석

### container-with-most-water

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n) | O(n) | ✅ |
| **Space** | O(1) | O(1) | ✅ |

**피드백**: 정확합니다! 배열을 한 번 순회(O(n))하며 상수 공간만 사용하는 최적의 풀이입니다.

### find-minimum-in-rotated-sorted-array

> ℹ️ 이 파일에는 **3가지 풀이**가 포함되어 있어 각각 분석합니다.

<details>
<summary>풀이 1: <code>findMin_use_math_min</code> — Time: ❌ O(n⁴) → O(n) / Space: ✅ O(n)</summary>

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n⁴) | O(n) | ❌ |
| **Space** | O(n) | O(n) | ✅ |

**피드백**: Math.min(...nums)는 spread 연산자로 인자를 펼치므로 O(n) 시간이며, 콜스택에 O(n) 공간이 필요합니다. 한번 다시 분석해보시는 것을 권장드립니다!

</details>

<details>
<summary>풀이 2: <code>findMin_naive</code> — Time: ❌ O(n³) → O(n) / Space: ✅ O(1)</summary>

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n³) | O(n) | ❌ |
| **Space** | O(1) | O(1) | ✅ |

**피드백**: 배열을 한 번 순회하는 단순 탐색이므로 시간복잡도는 O(n)입니다. 한번 다시 분석해보시는 것을 권장드립니다!

</details>

<details>
<summary>풀이 3: <code>findMin</code> — Time: ❌ O(n log n) → O(log n) / Space: ✅ O(1)</summary>

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n log n) | O(log n) | ❌ |
| **Space** | O(1) | O(1) | ✅ |

**피드백**: 이진 탐색으로 탐색 범위를 절반씩 줄이므로 O(log n)입니다. 한번 다시 분석해보시는 것을 권장드립니다!

</details>

### valid-parentheses

| | 유저 분석 | 실제 분석 | 결과 |
|---|---|---|---|
| **Time** | O(n) | O(n log n) | ❌ |
| **Space** | O(1) | O(n) | ❌ |

**피드백**: sort()를 사용하고 있어 시간 복잡도는 O(n log n)이며, 정렬 과정에서 O(n) 추가 공간이 필요합니다. 한번 다시 분석해보시는 것을 권장드립니다!

비기능 요구사항

• Cloudflare Workers 환경 (Node.js 모듈 불가, Web 표준 API만)
• 기존 OpenAI 유틸/패턴 재사용 (gpt-4.1-nano)
• 중복 댓글 방지 (HTML 마커: <!-- dalestudy-complexity-analysis -->)
• 기존 패턴 태깅과 병렬 실행 (Promise.allSettled)
• Non-blocking: 실패 시 전체 웹훅 처리 중단하지 않음

결정 완료

• 주석 포맷 표준: 자유 포맷 허용. 정해진 규칙 없이 유연하게 파싱
• R3 포함 여부: R1+R2+R3 모두 MVP에 포함
• 댓글 구조: R1/R2/R3을 한 댓글에 통합 (위 Output Format 참조)
• 불일치 시 톤 강도: 다시 풀어보는 것을 권장하는 톤
• 주석 파싱 실패 처리: 자유 포맷이므로 유연하게 대처. 파싱 불가 시 주석 없음으로 간주하여 분석값만 제공
• 멀티 풀이 처리: <details> 접기로 댓글 길이 관리. 풀이 1개는 기존 포맷, 2개 이상은 접기 적용. summary에 결과(✅/❌) 표시하여 접힌 상태에서도 핵심 정보 확인 가능

[devchanki]

아래 프롬프트 기반으로, Research.MD 를 생성해 보았습니다.

나는 현재 저장소에서 알고리즘 문제를 푼 PR이 올라오면 각 반영된 파일들을 가져와 시간 및 공간 복잡도를 분석해주는 요청을 open ai에게 요청해서 그 결과를 해당 PR에 댓글로 달아주는 기능을 구현하려 한다.

먼저 코드베이스를 조사하고 research.md를 작성해줘.
다음 내용을 포함해야 한다:
관련 기존 코드와 모듈,
현재 사용 중인 패턴 (캐싱, ORM 규칙 등),
이 기능이 영향을 줄 수 있는 영역,
재사용 가능한 기존 유틸리티

Research: PR 시간/공간 복잡도 분석 자동 댓글 기능

1. 관련 기존 코드와 모듈

핵심 참조 파일

파일	역할	재사용 가능성
handlers/tag-patterns.js	가장 유사한 기존 기능. PR 파일을 가져와 OpenAI로 알고리즘 패턴 분석 후 댓글 작성	구조 그대로 복사하여 변형
handlers/webhooks.js	웹훅 이벤트 라우팅. handlePullRequestEvent() (L211-279)에서 PR open/reopen/sync 시 tagPatterns() 호출	새 핸들러 호출 지점 추가
utils/openai.js	OpenAI API 호출 유틸. generatePatternAnalysis() (L95-175), generateCodeReview() (L15-85)	새 함수 추가
utils/prReview.js	getPRDiff(), postReviewComment(), postThreadReply() 등 PR 댓글 유틸	댓글 작성 함수 재사용 가능
utils/github.js	generateGitHubAppToken(), getGitHubHeaders()	그대로 재사용
utils/cors.js	corsResponse(), errorResponse()	그대로 재사용
utils/validation.js	validateOrganization(), hasMaintenanceLabel()	그대로 재사용
utils/constants.js	ALLOWED_ORG, MAINTENANCE_LABEL 등 상수	그대로 재사용
index.js	엔드포인트 라우팅	수동 호출 엔드포인트 추가 시 수정

가장 유사한 기존 구현: tag-patterns.js

이 핸들러가 새 기능과 거의 동일한 흐름:

1. PR 파일 목록 가져오기 (GET /pulls/{pr}/files)
2. 솔루션 파일 필터링 (SOLUTION_PATH_REGEX: /^[^/]+\/[^/]+\.[^.]+$/)
3. 이전 봇 댓글 삭제 (HTML 마커 기반: <!-- dalestudy-pattern-tag -->)
4. 각 파일의 raw content 가져오기 (file.raw_url, MAX_FILE_SIZE=20K)
5. OpenAI에 분석 요청 (generatePatternAnalysis)
6. 결과를 PR review comment로 작성 (subject_type: "file")

---

2. 현재 사용 중인 패턴

코드 아키텍처 패턴

• 핸들러 분리: 기능별 handlers/ 디렉토리에 독립 파일
• 유틸리티 공유: utils/ 디렉토리에 공통 로직
• 라우팅: index.js에서 pathname 기반 단순 라우팅
• 환경: Cloudflare Workers - Node.js 모듈 사용 불가, Web 표준 API만 사용

OpenAI 호출 패턴

• 모델: gpt-4.1-nano
• 패턴 분석용: temperature: 0.3, max_tokens: 500, response_format: { type: "json_object" }
• 코드 리뷰용: temperature: 0.7, max_tokens: 2000
• API 엔드포인트: https://api.openai.com/v1/chat/completions (직접 fetch)

봇 댓글 관리 패턴 (중복 방지)

기능	식별 방식	파일
Week 경고	user.type === "Bot" + body.includes("Week 설정이 누락")	prWeeks.js:109-114
패턴 태깅	user.type === "Bot" + body.includes("<!-- dalestudy-pattern-tag -->")	tag-patterns.js:125-127

PR 파일/댓글 관련 패턴

• 파일 목록: GET /repos/{o}/{r}/pulls/{pr}/files?per_page=100
• 파일 내용: file.raw_url로 직접 fetch + 20K 문자 제한
• Review Comment (파일별): POST /repos/{o}/{r}/pulls/{pr}/comments with subject_type: "file"
• Issue Comment (일반): POST /repos/{o}/{r}/issues/{pr}/comments

웹훅 트리거 패턴

• opened/reopened → 3초 대기 후 Week 체크 + 패턴 태깅
• synchronize → 패턴 태깅만
• OpenAI 기능은 env.OPENAI_API_KEY 존재 여부로 조건부 실행
• Non-blocking: try/catch로 실패해도 전체 처리 계속

---

3. 이 기능이 영향을 줄 수 있는 영역

영역	영향
PR 댓글	기존 패턴 태깅 + 새 복잡도 분석 → 파일당 댓글 2개로 증가. 별도 HTML 마커로 구분 필요
OpenAI API 비용	파일당 추가 API 호출 (패턴 + 복잡도 각각). gpt-4.1-nano라 비용은 낮음
웹훅 처리 시간	두 분석을 병렬(Promise.allSettled)로 실행하여 지연 최소화
GitHub API 호출	두 핸들러가 같은 파일 목록/내용을 각각 fetch → 약간의 중복이 있지만 독립성 유지를 위해 허용

---

4. 재사용 가능한 기존 유틸리티

즉시 재사용 (수정 없이)

유틸리티	위치	용도
generateGitHubAppToken(env)	github.js:68	GitHub 인증 토큰
getGitHubHeaders(token)	github.js:10	API 헤더
corsResponse(data, status)	cors.js:17	응답 래핑
errorResponse(message, status)	cors.js:39	에러 응답
validateOrganization(orgName)	validation.js:10	조직 검증
hasMaintenanceLabel(labels)	validation.js:17	라벨 체크
postReviewComment()	prReview.js:44	PR 댓글 작성

패턴 참고용 (구조 복사하여 변형)

패턴	위치	활용
PR 파일 목록 fetch + 필터링	tag-patterns.js:48-65	동일 로직
파일 raw content fetch + 크기 제한	tag-patterns.js:169-180	동일 로직
이전 봇 댓글 삭제	tag-patterns.js:106-154	새 마커로 동일 패턴
파일별 review comment 작성	tag-patterns.js:201-217	동일 API 호출
OpenAI JSON 응답 파싱	openai.js:95-175	동일 구조

[devchanki]

테스트 댓글입니다. 🤖