문제 개요
(m, c) 형태의 값 쌍을 담고 있는 리스트가 주어졌다고 가정해 보겠습니다. 각 쌍은 y = mx + c로 표현되는 하나의 직선을 나타냅니다. 여기에 두 값 l과 h도 함께 주어지며, 우리가 구해야 하는 것은 x = l부터 x = h까지의 구간에서 서로 교차하는 직선의 개수입니다.
예를 들어 입력이 다음과 같다면,
input_list = [[4, 6], [-6, 10], [8, 12]], l = 0, h = 2
출력은 2가 됩니다.
그림에서 볼 수 있듯이 직선 y = 4x + 6과 y = −6x + 10이 주어진 범위 안에서 서로 교차합니다. 교차하는 직선이 두 개이므로 정답은 2입니다.
접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다 −
- seg := 입력 리스트의 각 인덱스 i와 값 (m, c)에 대해 (m * l + c, m * h + c, i) 쌍을 담는 리스트를 만듭니다
- seg 리스트를 정렬합니다
- ans := input_list와 같은 크기의 0으로 채워진 새 리스트를 만듭니다
- c := seg로부터 만든 카운터(Counter) 맵을 준비합니다
- seg의 각 (x, y, i)에 대해 다음을 수행합니다
— c[x] > 1이면 ans[i] := 1 (시작·끝값이 완전히 일치하는 직선이 존재한다는 의미) - max_c := −(10^10), prv := −(10^10)으로 초기화합니다
- seg의 각 (x, y, i)에 대해 다음을 수행합니다
— x가 prv와 같으면 ans[i] := 1
— y ≤ max_c이면 ans[i] := 1
— max_c := max(max_c, y), prv := x로 갱신합니다 - min_c := 10^10, prv := 10^10으로 초기화합니다
- 역순으로 뒤집은 seg의 각 (x, y, i)에 대해 다음을 수행합니다
— x가 prv와 같으면 ans[i] := 1
— y ≥ min_c이면 ans[i] := 1
— min_c := min(min_c, y), prv := x로 갱신합니다 - ans 리스트 요소들의 합을 반환합니다
알고리즘이 동작하는 이유
핵심 아이디어는 각 직선을 구간 양 끝에서의 함수값, 즉 '왼쪽 끝값(m*l + c)'과 '오른쪽 끝값(m*h + c)'의 쌍으로 바꿔 표현하는 것입니다. 이렇게 하면 직선을 구간 [l, h] 위에 걸친 선분처럼 다룰 수 있습니다. 왼쪽 끝값 기준으로 정렬한 뒤 오른쪽 끝값을 차례로 검사할 때, 어떤 직선의 오른쪽 끝값이 지금까지 등장한 최댓값(max_c)보다 작거나 같다면 앞서 나온 직선과 순서가 역전된 것이므로 반드시 구간 안에서 교차합니다. 오른쪽에서 왼쪽 방향으로도 동일한 검사를 수행해 교차를 빠짐없이 찾아내며, 시작점과 끝점이 모두 같은 중복 직선 역시 서로 겹치므로 교차로 계산합니다. 전체 시간 복잡도는 정렬이 지배하므로 O(n log n)입니다.
예제 구현
더 잘 이해하기 위해 다음 구현을 살펴보겠습니다 −
from collections import Counter
def solve(input_list, l, h):
seg = [(m * l + c, m * h + c, i) for i, (m, c) in enumerate(input_list)]
seg.sort()
ans = [0 for _ in input_list]
c = Counter(seg)
for (x, y, i) in seg:
if c[x] > 1:
ans[i] = 1
max_c = -(10 ** 10)
prv = -(10 ** 10)
for (x, y, i) in seg:
if x == prv:
ans[i] = 1
if y <= max_c:
ans[i] = 1
max_c = max(max_c, y)
prv = x
min_c = 10 ** 10
prv = 10 ** 10
for (x, y, i) in seg[::-1]:
if x == prv:
ans[i] = 1
if y >= min_c:
ans[i] = 1
min_c = min(min_c, y)
prv = x
return sum(ans)
print(solve([[4, 6],[-6, 10],[8, 12]], 0, 2))입력
[[4, 6],[-6, 10],[8, 12]], 0, 2
출력
2