LeetCode 2566 문제 풀이: 숫자 재매핑을 통한 최대 차이 계산 (C++ | JavaScript | Python)

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

바이브코딩

대상자

• 초보 프로그래머 및 greedy 알고리즘/string manipulation 기초 학습자
• 난이도: 중간 (문자열 조작 및 그리디 전략 이해 필요)

핵심 요약

• 최대/최소 값 생성 전략:

- 최대값: 첫 번째 '9'가 아닌 숫자를 '9'로 변경 (예: 11891 → 99899)

- 최소값: 첫 번째 숫자를 '0'으로 변경 (예: 11891 → 890)

• 핵심 알고리즘:

- Greedy Strategy (가장 영향력 있는 자릿수 우선 조작)

- String Manipulation (replaceAll, replace 등 활용)

• 코드 예시:

- C++: getMax, getMin 함수 사용

- JavaScript: replaceAll 메서드 활용

- Python: str.replace 메서드 활용

섹션별 세부 요약

1. 문제 설명

• 입력: 숫자 num
• 제약 조건:

- 하나의 숫자만 모든 발생 위치에서 변경 가능

- 0으로 시작하는 수 허용

• 출력: 최대값 - 최소값 (예: 11891 → 99009)

2. 알고리즘 핵심 로직

• 최대값 생성:

- 첫 번째 non-'9' 숫자를 '9'로 대체

- 예: 11891 → 99899

• 최소값 생성:

- 첫 번째 숫자를 '0'로 대체

- 예: 11891 → 890

• Greedy 전략:

- 자릿수의 위치가 값에 미치는 영향을 고려하여 최적의 변경 지점 선택

3. 코드 구현 (C++/JavaScript/Python)

• C++:

- firstNotNineIndex 함수로 첫 번째 non-'9' 위치 탐색

- getMax, getMin 함수로 문자열 조작 후 stoi로 정수 변환

• JavaScript:

- find로 첫 번째 non-'9' 찾고 replaceAll로 대체

• Python:

- next로 첫 번째 non-'9' 찾고 str.replace로 처리

4. 테스트 케이스

• num = 11891 → 99009
• num = 90 → 99
• num = 999 → 999 (모든 숫자가 '9' → 변경 불가)
• num = 1000 → 9000 - 0 = 9000

5. 시간/공간 복잡도

• 시간 복잡도: O(n) (문자열 순회 및 변경)
• 공간 복잡도: O(1) (변수 사용량 제한)

결론

• 실무 팁:

- 최대값 생성 시 첫 번째 non-'9'를 '9'로, 최소값 생성 시 첫 번째 자릿수를 '0'으로 변경

- Leading zero 허용 시 0로 시작하는 수도 처리 가능

• 예시 코드:

- def minMaxDifference(num: int) -> int: s = str(num); to9 = next((c for c in s if c != '9'), s[0]); to0 = s[0]; return int(s.replace(to9, '9')) - int(s.replace(to0, '0'))