정수 num이 하나 주어져 있다고 가정해 봅시다. 우리는 아래의 연산을 정확히 두 번 적용해야 합니다.
- 0부터 9 사이의 숫자 x를 하나 선택합니다.
- 0부터 9 사이의 또 다른 숫자 y를 선택합니다. 이때 y는 x와 같아도 됩니다.
- num의 십진수 표현에서 x가 등장하는 모든 자릿수를 y로 바꿉니다. 단, 새로 만들어지는 정수는 선행 0(leading zero)을 가질 수 없으며, 값이 0이 되어서도 안 됩니다.
첫 번째 연산의 결과를 a, 두 번째 연산의 결과를 b라고 할 때, a와 b 사이의 최대 차이를 구하는 것이 이 문제의 목표입니다.
문제 예시
예를 들어 입력이 555라면 출력은 888이 됩니다.
- 첫 번째 연산: x = 5, y = 9를 선택 → 결과를 a에 저장
- 두 번째 연산: x = 5, y = 1을 선택 → 결과를 b에 저장
그러면 a = 999, b = 111이 되고, 최대 차이는 다음과 같습니다.
999 − 111 = 888
풀이 접근 방법
핵심 아이디어는 간단합니다. 한 번의 연산으로 만들 수 있는 가장 큰 수와 가장 작은 수를 각각 구한 뒤, 그 차이를 반환하면 됩니다.
1. 최댓값 만들기 — getMax()
- 숫자를 문자열로 변환합니다.
- 왼쪽부터 탐색하며 '9'가 아닌 첫 번째 자릿수를 찾습니다.
- 그 자릿수를 모두 '9'로 바꾸면 만들 수 있는 가장 큰 수를 얻습니다.
2. 최솟값 만들기 — getMin()
- 첫 번째 자릿수가 '1'이 아니라면, 첫 번째 자릿수를 모두 '1'로 바꿉니다. 이렇게 하면 선행 0 없이 가장 작은 수를 만들 수 있습니다.
- 첫 번째 자릿수가 이미 '1'이라면, 두 번째 자릿수부터 '1'보다 큰 첫 번째 자릿수를 찾아 해당 숫자를 모두 '0'으로 바꿉니다.
- 만약 수가 한 자리라면 1을 그대로 반환합니다.
3. 메인 로직 — maxDiff()
- a = getMax(num), b = getMin(num)을 각각 계산합니다.
- |a − b|를 반환합니다.
C++ 구현 예제
아래 구현을 통해 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int getMax(int x){
string s = to_string(x);
char a = '9', b;
int i = 0;
while (i < s.size() && s[i] == '9')
i++;
if (i < s.size())
a = s[i];
for (int i = 0; i < s.size(); i++) {
if (s[i] == a) {
s[i] = '9';
}
}
return stoi(s);
}
int getMin(int x){
string s = to_string(x);
char a;
if (s[0] != '1') {
a = s[0];
for (int i = 0; i < s.size(); i++) {
if (s[i] == a) {
s[i] = '1';
}
}
}
else {
if (s.size() == 1) {
return 1;
}
int i = 0;
a = '1';
while (i < s.size() && s[i] <= '1')
i++;
if (i < s.size())
a = s[i];
for (int i = 1; i < s.size(); i++) {
if (s[i] == a) {
s[i] = '0';
}
}
}
return stoi(s);
}
int maxDiff(int num) {
int a = getMax(num);
int b = getMin(num);
return abs(a - b);
}
};
main(){
Solution ob;
cout << (ob.maxDiff(666));
}입력
666
출력
888
입력 666의 경우, 최댓값 연산으로 666 → 999(a)를 만들 수 있고, 최솟값 연산으로 666 → 111(b)을 만들 수 있습니다. 따라서 최대 차이는 999 − 111 = 888이 됩니다.