개미 수열 (Look and Say)

양의 정수 n(과제 조건: 3 < n < 100)이 주어질 때, 개미 수열의 n번째 항 Ln 문자열에서 가운데 두 자리를 구하는 과제 구현입니다.

---

과제 체크포인트

Phase 1: 문제 정의와 환경

• 개미 수열 규칙에 따른 buildNextTerm (다음 항 생성)
• buildNthTerm으로 Ln 생성
• 짝수 길이 문자열의 가운데 두 자리 getMiddleTwoDigits
• 최종 solve(n) — 예시 n = 5 → 12, n = 8 → 21

Phase 2: 테스트 주도 개발 (TDD)

• Vitest 설정 (globals: true, Node 환경)
• 단위 테스트: buildNextTerm, buildNthTerm, getMiddleTwoDigits
• 통합 테스트: solve 예시 검증

Phase 3: 다른 처리 방식 (다양한 풀이)

• lookAndSayAlternative.ts: 정규식으로 연속 구간 분리 + 재귀로 Ln
• solveWithRegexAndRecursion 및 단위 테스트

Phase 4: 교차 검증

• 두 구현이 여러 n에서 동일한 결과를 내는지 통합 테스트 (twoImplementationsAgree.spec.ts)

---

문제 요약

• L1 = 1로 시작합니다.
• 이전 항을 왼쪽부터 읽되, 같은 숫자가 연속된 구간마다 (구간의 길이)(그 숫자 한 자리)를 이어 붙여 다음 항을 만듭니다.
• 예: L5 = 111221 → 가운데 두 자리는 12.

프로젝트 구조

src/
  lookAndSay.ts              # 풀이 1: 순회로 next 항, 반복문으로 n번째 항
  lookAndSayAlternative.ts   # 풀이 2: 정규식으로 next 항, 재귀로 n번째 항
  tests/
    unit/                    # 단위 테스트 (함수별)
    integration/             # 통합 테스트 (solve, 대안 solve, 두 구현 일치)
package.json
vitest.config.ts
tsconfig.json

풀이 1 — lookAndSay.ts (명령형 순회)

• buildNextTerm: 문자열을 한 번 훑으며 연속 구간의 길이와 숫자를 누적해 다음 항 문자열을 만듭니다.
• buildNthTerm: L1 = "1"에서 시작해 n - 1번 buildNextTerm을 적용합니다.
• getMiddleTwoDigits: 길이가 짝수일 때, 중앙 기준 앞뒤 한 자리씩(slice(mid - 1, mid + 1)).
• solve: buildNthTerm → getMiddleTwoDigits.

풀이 2 — lookAndSayAlternative.ts (정규식 + 재귀)

• buildNextTermWithRegex: (\d)\1*로 run을 나눈 뒤 길이 + 첫 숫자로 매핑.
• buildNthTermRecursive: L1 = "1", Ln = next(Ln-1)를 재귀로 표현. getMiddleTwoDigits는 풀이 1에서 import.
• solveWithRegexAndRecursion: 위 조합.

두 풀이는 같은 정의를 따르므로 동일 n에 대해 결과가 같아야 하며, 테스트로 검증합니다.

복잡도 (개략)

Ln의 문자열 길이를 ( \ell )이라 하면:

• 한 번의 next 항: 시간 ( O(\ell) ), 새 문자열 생성에 따른 추가 공간 ( O(\ell) ).
• n번째 항까지: 단계마다 길이가 늘어나므로 단계별 길이 합에 비례합니다. 본 구현은 문자열로 한 자리씩 이어 붙이며, 정수로 값을 환산하지 않습니다(코드와 일치).

재귀 풀이는 호출 스택 ( O(n) ). n < 100에서는 보통 무난하고, n이 매우 커지면 반복문 버전이 스택 측면에서 유리할 수 있습니다.

실행 방법

npm install
npm test
npm run test:watch   # 감시 모드
npm run typecheck    # 타입 검사만

---

과제 셀프회고

개미 수열 과제에 대한 회고

문제를 처음 읽었을 때는 “이전 항을 어떻게 읽을지”만 정하면 구현은 단순하다고 느꼈습니다. 연속 구간을 직접 세는 방식이 디버깅에 유리했고, 같은 규칙을 정규식으로 옮기면 코드는 짧아지지만 패턴을 읽을 줄 알아야 한다는 장·단점을 비교할 수 있었습니다.

과제에서 요구한 테스트 주도 개발(TDD)에 맞추려고, buildNextTerm·getMiddleTwoDigits 등 단위 테스트와 예시 입력의 기대값을 먼저 적은 뒤 구현을 맞췄습니다. 통합 테스트와 두 구현 일치 검사는 이후에 리그레션을 막기 위해 추가했습니다.

n이 커질수록 항의 문자열 길이가 빠르게 늘어난다는 점은 효율 논의에서 빼놓을 수 없습니다. 복잡도를 쓸 때 “큰 정수는 BigInt로…”라고 말하기 쉬운데, 실제 코드는 BigInt 없이 문자열로만 자릿수를 쌓습니다. 과제 예시(n = 5, 8)와 테스트에서 돌려 본 여러 n에서는 Ln 길이가 짝수가 되어 가운데 두 자리를 구할 수 있었습니다. 임의의 n에서 항상 짝수 길이라고 단정하지는 않았고, getMiddleTwoDigits는 길이가 홀수면 오류를 내도록 두었습니다.

이번 범위에서는 정확성과 가독성, 그리고 함수 단위로 테스트 가능한 구조를 우선했습니다.

아하! 모먼트 (A-ha! Moment)

• 연속 숫자 덩어리를 “세는 루프”로도, “정규식으로 잘라 배열로”도 같은 결과로 표현할 수 있다는 점이 정리되었을 때, 한 문제에 여러 해법이 있다는 게 손에 잡혔습니다.
• README에 복잡도를 쓰다가 “문자열 vs BigInt”를 구분하지 않으면 구현과 설명이 어긋날 수 있다는 것도 조금이나마 깨달았습니다.

기술적 성장

• Vitest로 단위·통합 테스트를 나누고, 두 구현의 출력을 같은 케이스에서 비교하는 패턴을 연습했습니다.
• TypeScript로 문자열 인덱싱·슬라이스를 명시적으로 다루면서, “숫자 한 자리”를 정수 타입으로 쌓지 않고 푸는 이유를 설명할 수 있게 되었습니다.

코드 품질

만족스러운 부분

• buildNextTerm → buildNthTerm → getMiddleTwoDigits → solve로 단계가 분리되어 있어 테스트와 설명이 쉽습니다.
• 대안 풀이 파일을 분리하고, getMiddleTwoDigits만 공유해 중복을 줄였습니다.
• 통합 테스트로 두 구현이 여러 n에서 일치하는지 확인합니다.

리팩토링하고 싶은 부분

• validatePositiveInteger가 두 파일에 비슷하게 있습니다. 공통 유틸로 빼면 중복은 줄지만, 과제 제출 단위와 파일 수를 고려해 현재는 유지했습니다.
• n이 매우 클 때의 메모리·시간을 다루려면 별도 실험이 필요합니다. 과제 범위 밖이라 진행하지 않았습니다.

학습 효과 분석

테스트 코드를 통한 구현 방향 잡기

예시(n = 5 → "12", n = 8 → "21")와 단위 테스트의 expect 값을 기준으로 역으로 “중간 함수가 어떤 문자열을 내야 하는지”를 좁혀 갔습니다. 특히 getMiddleTwoDigits는 입력 문자열이 짝수일 때만 의미가 있으므로, 실패 케이스(홀수 길이)를 테스트에 넣어 두면 구현이 흔들리지 않습니다.

과제 셀프 리뷰

좋았던 점

• 규칙이 명확해, 알고리즘 자체는 구현 난이도가 과하지 않았습니다.
• 두 가지 스타일(순회 vs 정규식+재귀)을 나란히 두고 비교할 수 있었습니다.

어려웠던 점

• 처음에는 Vitest 버전·전역(describe 등) 설정 이슈로 테스트가 안 돌았는데, 도구 의존성과 설정을 맞추는 데 시간이 들었습니다.