문제 소개
이 튜토리얼에서는 숫자의 자릿수를 단 한 번만 교체(swap)하여 만들 수 있는 가장 큰 짝수를 찾는 프로그램을 C++로 작성해 보겠습니다.
어떤 수가 짝수가 되려면 마지막 자릿수가 반드시 짝수여야 합니다. 따라서 적절한 짝수 자릿수를 골라 마지막 자릿수와 맞바꾸되, 숫자 전체의 손실을 최소화하는 위치를 선택하는 것이 이 문제의 핵심입니다.
문제 해결 단계
다음 순서대로 문제를 해결할 수 있습니다.
- 숫자를 문자열(string) 형태로 초기화합니다.
- 주어진 숫자를 왼쪽부터 차례로 순회합니다.
- 마지막 자릿수보다 작거나 같은 짝수 자릿수를 찾아 값과 위치를 기록합니다.
- 조건에 맞는 짝수 자릿수를 찾으면 즉시 반복문을 종료합니다.
- 탐색이 끝날 때까지 짝수 자릿수가 하나도 없었다면, 주어진 숫자를 그대로 반환합니다.
- 위 단계에서 찾은 짝수 자릿수와 마지막 자릿수를 서로 교체(swap)합니다.
- 변환된 숫자를 반환합니다.
구현 코드
#include <bits/stdc++.h>
using namespace std;
// 한 번의 자리 교체로 얻을 수 있는 가장 큰 짝수를 반환하는 함수
string getLargestEvenNumber(string number, int n) {
int even = INT_MAX, index;
for (int i = 0; i < n - 1; i++) {
// 짝수 자릿수를 발견하면 값과 위치를 기록
if ((number[i] - '0') % 2 == 0) {
even = (number[i] - '0');
index = i;
}
// 마지막 자릿수 이하의 짝수를 찾았다면 더 볼 필요 없음
if (even <= (number[n - 1] - '0')) {
break;
}
}
// 짝수 자릿수가 하나도 없었다면 원본을 그대로 반환
if (even == INT_MAX) {
return number;
}
// 찾은 짝수 자릿수와 마지막 자릿수를 교체
swap(number[index], number[n - 1]);
return number;
}
int main() {
string number = "15433";
cout << getLargestEvenNumber(number, 5) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력을 확인할 수 있습니다.
15334
동작 과정 살펴보기
예제 입력 "15433"으로 흐름을 정리해 보겠습니다.
- 마지막 자릿수는 3입니다.
- 왼쪽부터 탐색하면 처음 만나는 짝수 자릿수는 인덱스 2의 4입니다. 4는 3보다 크므로 반복문은 종료되지 않고 계속 진행됩니다.
- 탐색이 끝날 때까지 기록된 짝수 자릿수는 4뿐이므로, 4와 마지막 자릿수 3을 교체합니다.
- 최종 결과는 "15334"가 됩니다.
참고로, 마지막 자릿수보다 작거나 같은 짝수 자릿수가 여러 개 있다면 이 알고리즘은 가장 왼쪽에 있는 것을 선택하고, 모든 짝수 자릿수가 마지막 자릿수보다 크다면 탐색 종료 시점에 기록된 가장 오른쪽 짝수 자릿수를 사용하게 됩니다. 두 경우 모두 숫자의 값이 최대한 크게 유지되도록 하는 그리디(greedy) 전략입니다.
시간 복잡도
이 알고리즘은 문자열을 한 번만 선형으로 순회하므로 시간 복잡도는 O(n)이며, 별도의 추가 메모리를 사용하지 않으므로 공간 복잡도는 O(1)입니다.
마무리
이 튜토리얼을 진행하면서 궁금한 점이 생기면 댓글로 남겨 주세요.