문제 개요
두 개의 문자열 S와 T가 주어집니다. 각 문자열은 하나의 양의 유리수를 나타내며, 두 문자열이 서로 같은 수를 표현하고 있는지 판별해야 합니다. 문자열에는 유리수의 순환 소수 부분을 나타내기 위해 괄호가 사용될 수 있습니다.
유리수는 최대 세 부분으로 구성할 수 있습니다. 바로 정수부, 순환하지 않는 소수부(비순환부), 그리고 순환 소수부입니다. 따라서 수는 다음 세 가지 형태 중 하나로 표현됩니다.
정수부만 있는 경우 (예: 0, 12, 123)
정수부.비순환부 형태 (예: 0.5, 1.0, 2.12, 2.0001)
정수부.비순환부(순환부) 형태 (예: 0.1(6), 0.9(9), 0.00(1212))
예를 들어 0.1(6), 0.1666(6), 0.166(66)은 모두 1/6을 나타내는 올바른 표현입니다.
입력이 S = "0.(52)", T = "0.5(25)"라고 해보겠습니다. 0.(52)는 0.525252...이고, 0.5(25) 역시 0.5252525...이므로 두 값은 같습니다. 따라서 출력은 True가 됩니다.
접근 방법
이 문제는 각 문자열을 일반적인 소수 형태로 확장한 뒤 실수 값으로 비교하는 방식으로 해결할 수 있습니다. 핵심 아이디어는 순환부를 충분히 많이 반복해 붙이면, 표현 방식이 달라도 같은 유리수라면 동일한 소수 전개로 수렴한다는 점입니다.
구체적인 해결 단계는 다음과 같습니다.
f() 함수를 정의합니다. 이 함수는 문자열 S를 입력받습니다.
S에서 '(' 의 위치 인덱스 i를 찾습니다.
i가 유효한 범위 내에 존재한다면:
base := S의 인덱스 0부터 i-1까지의 부분 문자열 (괄호 앞까지의 소수)
rep := '(' 다음부터 닫는 괄호 ')' 앞까지의 부분 문자열 (순환부)
j를 0부터 19까지 반복하면서 base 뒤에 rep을 계속 이어 붙여 순환부를 20번 확장합니다.
확장된 base를 실수(double) 값으로 변환해 반환합니다.
'(' 가 없다면 순환 소수가 없는 것이므로, S를 그대로 실수 값으로 변환해 반환합니다.
메인 로직에서는 f(S)와 f(T)의 값이 같으면 true를, 아니면 false를 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isRationalEqual(string S, string T){
return f(S) == f(T);
}
double f(string S){
auto i = S.find("(");
if (i != string::npos) {
string base = S.substr(0, i);
string rep = S.substr(i + 1, S.length() - i - 2);
for (int j = 0; j < 20; ++j)
base += rep;
return stod(base);
}
return stod(S);
}
};
main(){
Solution ob;
cout << (ob.isRationalEqual("0.(52)", "0.5(25)"));
}
입력
"0.(52)", "0.5(25)"
출력
1
동작 원리 및 참고 사항
위 코드에서 f() 함수는 먼저 find()를 통해 여는 괄호 '('의 위치를 찾습니다. 괄호가 존재하면 substr()으로 괄호 앞의 고정된 소수 부분(base)과 괄호 안의 순환부(rep)를 분리한 뒤, rep을 20번 반복해 이어 붙입니다. 예를 들어 "0.5(25)"는 "0.5" + "25"×20 형태의 긴 소수 문자열로 확장됩니다.
순환부를 충분히 길게 반복하면 두 표현이 같은 유리수일 경우 double 타입에서 동일한 값으로 수렴하므로, 단순히 == 연산자로 비교해도 올바른 결과를 얻을 수 있습니다. 출력이 1(true)로 나타난 것을 통해 "0.(52)"와 "0.5(25)"가 같은 유리수임을 확인할 수 있습니다.