문제 설명
정수 n이 하나 주어집니다. 우리는 분모가 n 이하이면서 0과 1 사이(경계값 제외)에 있는 모든 기약분수(simplified fraction)의 목록을 구해야 합니다. 분수들은 어떤 순서로 나열되어도 상관없습니다.
예를 들어 입력이 n = 4라면 출력은 ["1/2", "1/3", "1/4", "2/3", "3/4"]가 됩니다. "2/4"는 "1/2"로 약분할 수 있기 때문에 기약분수가 아니며, 따라서 목록에 포함되지 않습니다.
접근 방법
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
- 결과를 저장할 배열 ret을 정의합니다.
- 바깥 루프: i를 2부터 n까지 반복합니다.
- 안쪽 루프: j를 1부터 i-1까지 반복합니다.
- c := i와 j의 최대공약수(gcd)를 계산합니다.
- a := j / c, b := i / c로 약분된 분자와 분모를 구합니다.
- "a/b" 형태의 문자열을 만들어 ret의 끝에 추가합니다.
- 마지막으로 ret에서 중복을 제거한 배열을 반환합니다.
동작 원리
분자 j와 분모 i의 최대공약수를 구해 각각 나누면 항상 기약분수 형태가 됩니다. 예를 들어 (i = 4, j = 2)인 경우 gcd는 2이므로 2/4 → 1/2가 되어 이미 저장된 값과 중복됩니다. set 자료구조를 사용하면 이러한 중복을 손쉽게 제거할 수 있습니다.
참고로, gcd(i, j) == 1인 경우에만 문자열을 추가하도록 조건을 걸면 set 없이도 중복 없는 결과를 바로 얻을 수 있어 더 효율적인 구현이 가능합니다.
예제 코드 (C++)
다음 구현을 통해 동작 방식을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> simplifiedFractions(int n) {
vector<string> ret;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
int c = __gcd(i, j);
int a = j / c;
int b = i / c;
ret.push_back(to_string(a) + "/" + to_string(b));
}
}
set<string> s(ret.begin(), ret.end());
return vector<string>(s.begin(), s.end());
}
};
main(){
Solution ob;
print_vector(ob.simplifiedFractions(4));
}
입력
4
출력
[1/2, 1/3, 1/4, 2/3, 3/4]
시간 복잡도
두 개의 중첩 루프가 총 O(n²)번 실행되고, 각 반복마다 최대공약수 계산에 O(log n)이 소요되므로 전체 시간 복잡도는 O(n² log n)입니다. 공간 복잡도는 결과를 저장하는 데 필요한 공간에 비례합니다.