세 개의 숫자가 주어졌을 때, 앞의 두 숫자가 가진 배수들을 모두 모아 정렬한 목록에서 n번째 배수를 찾는 문제입니다. 예시를 통해 좀 더 자세히 살펴보겠습니다.
예제 이해하기
입력
x = 2 y = 3 n = 7
출력
10
2의 처음 n개 배수는 2, 4, 6, 8, 10, 12, 14이고, 3의 처음 n개 배수는 3, 6, 9, 12, 15, 18, 21입니다.
두 목록을 하나로 합치고 중복을 제거한 뒤 오름차순으로 정렬하면 2, 3, 4, 6, 8, 9, 10, 12, 14, 15, 18, 21이 됩니다. 이 목록에서 n번째(여기서는 7번째) 값은 10입니다.
알고리즘
- 모든 배수를 저장할 벡터(vector)를 초기화합니다.
- x의 처음 n개 배수를 구해 벡터에 차례대로 추가합니다.
- y의 처음 n개 배수를 하나씩 확인하면서, 벡터에 아직 존재하지 않는 값만 추가합니다.
- 배수 전체를 오름차순으로 정렬합니다.
- 정렬된 벡터에서 n번째 요소를 결과로 반환합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다. y의 배수를 추가하기 전에 binary_search 함수로 중복 여부를 먼저 검사한다는 점이 핵심입니다.
#include<bits/stdc++.h>
using namespace std;
int findNthMultiple(int x, int y, int n) {
vector<int> multiples;
for (int i = 1; i <= n; i++) {
multiples.push_back(x * i);
}
sort(multiples.begin(), multiples.end());
for (int i = 1, k = n; i <= n && k; i++) {
if (!binary_search(multiples.begin(), multiples.end(), y * i)) {
multiples.push_back(y * i);
sort(multiples.begin(), multiples.end());
}
}
return multiples[n - 1];
}
int main() {
int x = 2, y = 3, n = 7;
cout << findNthMultiple(x, y, n) << endl;
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 결과를 얻을 수 있습니다.
10
성능에 대한 참고 사항
위 구현에서는 y의 배수를 새로 추가할 때마다 벡터 전체를 다시 정렬하므로, 입력 크기가 커질수록 정렬 비용이 반복적으로 발생합니다. 두 수의 배수는 각각 이미 오름차순으로 정렬되어 있으므로, 투 포인터(two-pointer) 기법으로 두 배수 열을 한 번에 병합하면서 중복을 건너뛰면 훨씬 효율적으로 문제를 해결할 수 있습니다. 작은 입력에서는 현재 구현으로도 충분하지만, 성능이 중요한 상황에서는 병합 방식의 개선을 고려해 보시기 바랍니다.