AI 리뷰 봇의 공간 복잡도 평가 기준 관련 제안 #68

안녕하세요. 리트코드 스터디 봇의 공간 복잡도 채점 기준과 관련하여 제안할 사항이 있어 이슈를 열었습니다.

상황 설명

리트코드 스터디 중 SC(Space Complexity)에 대한 설명을 작성한 주석에 피드백을 받았습니다.

당시 재귀 호출로 인해 발생하는 스택 메모리를 공간 복잡도 계산에서 누락했는데,
이전에 AI 리뷰 봇으로부터 기존에 작성한 SC 설명이 옳다는 판정을 받은 적이 있어
관련 내용을 공유드립니다.

문제 정의

제가 작성한 코드와 이전에 받은 AI 봇 채점은 다음과 같습니다.

// SC: O(1) - 새로 쓰는 변수 없음
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 먼저 sorting
        // ... 이하 생략
    }
};

• 당시 AI 리뷰 봇은 O(1)이라는 공간 복잡도 판정을 옳다고 평가했습니다.
  • 다만 std::sort()의 재귀 스택은 공간 복잡도 채점 기준에 고려되지 않은 것으로 보입니다.
• 현재는 새로운 주석을 작성하여 커밋된 상태라 기존 채점 결과를 다시 확인하기는 어려운 상황입니다.

제안 사항

공간 복잡도를 평가할 때 재귀 호출에 의해 발생하는 스택 메모리도 고려하도록 채점 기준을 보완할 수 있을지 제안드립니다.

참고

참고하실 리뷰는 여기에서 확인해주시면 됩니다.