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

[devchanki]

목표

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

요구사항

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) |

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

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

비기능 요구사항

• 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 참조)
• 불일치 시 톤 강도: 다시 풀어보는 것을 권장하는 톤
• 주석 파싱 실패 처리: 자유 포맷이므로 유연하게 대처. 파싱 불가 시 주석 없음으로 간주하여 분석값만 제공

참고

• 상세 리서치는 댓글의 Research.md 참조
• 가장 유사한 기존 구현: handlers/tag-patterns.js

[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]

테스트 댓글입니다. 🤖