직선의 방정식 y = mx + c가 주어졌을 때, 배열에 있는 값들로 만들 수 있는 순서쌍(ordered pair) 중 이 방정식을 만족하는 쌍의 개수를 구하는 문제입니다. 배열과 기울기 m, 절편 c가 입력으로 주어지며, 조건을 만족하는 순서쌍의 개수를 출력해야 합니다.
먼저 예시를 통해 문제를 살펴보겠습니다.
입력 예시
arr = [1, 2, 3] m = 1 c = 1
출력 예시
2
위 예시에서 방정식 y = x + 1을 만족하는 순서쌍은 다음과 같습니다.
(2, 1) (3, 2)
배열의 각 원소를 x값으로 대입했을 때, 결과인 y값도 같은 배열 안에 존재하는 경우를 세면 됩니다. 예를 들어 x = 1이면 y = 2가 되는데, 2는 배열에 있지만 순서쌍 (1, 2)는 'y = mx + c' 형태에서 arr[j] == m * arr[i] + c 조건으로 검사하는 방식에 따라 카운트 여부가 결정됩니다.
알고리즘
- 배열(arr), 기울기(m), 절편(c)을 초기화합니다.
- 두 개의 반복문을 사용하여 배열에서 만들 수 있는 모든 순서쌍을 탐색합니다.
- 각 순서쌍이 직선의 방정식을 만족하는지 검사합니다.
- 검사 방법은 해당 값을 직선의 방정식에 대입하여 등식이 성립하는지 확인하는 것입니다.
- 방정식을 만족하는 순서쌍이라면 카운트를 1 증가시킵니다.
- 모든 탐색이 끝나면 최종 카운트를 반환합니다.
C++ 구현
다음은 위 알고리즘을 C++로 구현한 코드입니다.
#include <bits/stdc++.h>
using namespace std;
bool isSatisfyingLineEquation(int arr[], int i, int j, int m, int c) {
if (i == j) {
return false;
}
return arr[j] == m * arr[i] + c;
}
int getOrderedPointsPairCount(int arr[], int n, int m, int c) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (isSatisfyingLineEquation(arr, i, j, m, c)) {
count++;
}
}
}
return count;
}
int main() {
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = 10;
int m = 1, c = 1;
cout << getOrderedPointsPairCount(arr, n, m, c) << endl;
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
9
코드 설명 및 시간 복잡도
isSatisfyingLineEquation 함수는 인덱스 i와 j가 같은 경우를 제외한 뒤, arr[i]를 x값으로 대입했을 때 계산되는 y값(m * arr[i] + c)이 arr[j]와 일치하는지 확인합니다. 즉, 점 (arr[i], arr[j])가 직선 위에 존재하는지 판별하는 역할을 합니다.
getOrderedPointsPairCount 함수는 이중 반복문을 통해 가능한 모든 순서쌍을 검사하므로 시간 복잡도는 O(n²)입니다. 배열의 크기가 크다면 해시 맵(예: unordered_map)을 활용해 각 x값에 대응하는 y값의 존재 여부를 O(1)에 조회함으로써 O(n)까지 최적화할 수 있습니다.