C++로 두 선분에서 서로 다른 두 점 찾는 방법

문제 개요

x축 위에 두 개의 구간이 있다고 가정해 보겠습니다. 첫 번째 구간은 (l1, r1), 두 번째 구간은 (l2, r2)로 표현되며, 각각 l1 < r1과 l2 < r2 조건을 만족합니다. 이 두 선분은 서로 교차할 수도, 일부만 겹칠 수도 있고, 완전히 일치하는 경우도 있습니다.

목표는 다음 조건을 모두 만족하는 두 수 a와 b를 찾는 것입니다.

• a는 구간 (l1, r1) 안에 속해야 합니다.
• b는 구간 (l2, r2) 안에 속해야 합니다.
• a와 b는 서로 달라야 합니다.

예를 들어 입력이 l1 = 2, r1 = 6, l2 = 3, r2 = 4라고 한다면, a = 2, b = 3을 답으로 선택할 수 있으며, 이 외에도 정답이 될 수 있는 조합은 여러 가지가 존재합니다.

풀이 접근법

이 문제는 아주 간단한 관찰 하나로 해결할 수 있습니다. 바로 두 선분의 왼쪽 끝점 l1과 l2를 비교하는 것입니다.

1. l1과 l2가 같다면, l1을 1 증가시킵니다. 이렇게 하면 l1은 여전히 자신의 구간 범위 안에 있으면서 l2와 다른 값을 가지게 됩니다.
2. 이후 l1과 l2를 결과로 출력합니다.

두 값이 처음부터 다르다면 그대로 사용하면 되고, 같은 경우에는 한쪽을 1만 늘려주면 되기 때문에 상수 시간 O(1) 만에 답을 구할 수 있는 매우 효율적인 방법입니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

void solve(int l1, int r1, int l2, int r2) {
    if (l1 == l2)
        l1++;
    cout << l1 << ", " << l2;
}
int main() {
    int l1 = 2;
    int r1 = 6;
    int l2 = 3;
    int r2 = 4;
    solve(l1, r1, l2, r2);
}

입력

2, 6, 3, 4

출력

2, 3

동작 설명

위 예제에서 l1 = 2와 l2 = 3은 이미 서로 다르기 때문에 조건문(if l1 == l2)은 실행되지 않습니다. 따라서 프로그램은 그대로 2와 3을 출력합니다. 2는 구간 [2, 6]에 속하고, 3은 구간 [3, 4]에 속하며 두 값이 서로 다르므로 문제의 모든 조건을 충족하는 유효한 정답이 됩니다.