안녕하세요! 이번 포스트에서는 파이썬을 이용한 코딩 테스트의 한 문제인 “선분을 그룹으로 나누기”에 대해 설명하겠습니다. 이 문제는 선분을 적절히 그룹으로 나누는 알고리즘을 설계하고 구현하는 연습을 포함하고 있습니다. 문제를 통해 선분을 다루는 기본적인 사고 방식을 익힐 수 있으며, 알고리즘적인 사고를 증진시킬 수 있습니다.
문제 설명
어떤 직선상의 선분들이 주어집니다. 각각의 선분은 시작점과 끝점으로 표현됩니다. 이때, 선분들이 서로 겹치거나 바로 붙은 경우 같은 그룹으로 묶습니다. 선분 리스트가 주어졌을 때, 몇 개의 서로 다른 그룹으로 나눌 수 있는지를 계산하는 문제입니다. 예를 들어, 다음과 같은 선분들이 있을 때:
[(1, 5), (2, 3), (6, 8), (7, 10)]
위의 선분들은 다음과 같이 그룹으로 나누어질 수 있습니다:
그룹 1: [(1, 5), (2, 3)]
그룹 2: [(6, 8), (7, 10)]
입력/출력 형식
입력
첫 번째 줄에 선분의 개수 n (1 ≤ n ≤ 100,000)이 주어집니다. 그 다음 n개의 줄에 각각의 선분의 시작점과 끝점 (start, end)이 주어집니다. 끝점은 항상 시작점보다 크다고 가정합니다.
출력
서로 겹치는 선분 그룹의 개수를 출력합니다.
문제 해결 접근 방식
이 문제를 해결하기 위해, 선분을 정렬하고 그룹으로 나누는 방법을 생각해 볼 수 있습니다. 일반적인 접근 방식은 다음과 같습니다:
- 선분들을 시작점 기준으로 정렬합니다. 만약 시작점이 같다면 끝점을 기준으로 정렬합니다.
- 정렬된 선분들을 순회하면서, 현재 선분의 끝점이 이전 선분의 끝점보다 크거나 같으면 같은 그룹으로 묶습니다.
- 그룹의 개수를 세어 최종 결과를 출력합니다.
구현
이제 위의 접근 방식을 바탕으로 파이썬으로 코드를 구현해 보겠습니다. 코드는 다음과 같습니다:
def count_groups(segments):
# 선분을 시작점으로 정렬하고 시작점이 같으면 끝점 기준으로 정렬
segments.sort(key=lambda x: (x[0], x[1]))
groups = 0
current_end = -1
for start, end in segments:
if start > current_end:
# 새로운 그룹이 시작된다.
groups += 1
current_end = end
else:
# 현재 그룹에 포함된다.
current_end = max(current_end, end)
return groups
# 입력 받기
n = int(input())
segments = [tuple(map(int, input().split())) for _ in range(n)]
result = count_groups(segments)
print(result)
코드 설명
위 코드는 다음과 같은 방식으로 동작합니다:
segments.sort(): 선분 리스트를 정렬합니다. 이때 키를 설정하여 시작점으로 정렬하고, 시작점이 같으면 끝점으로 정렬합니다.- 변수
groups: 그룹의 개수를 세기 위한 변수로 초기값을 0으로 설정합니다. - 변수
current_end: 현재 그룹의 끝점을 추적하기 위한 변수입니다. 초기값은 -1로 설정되었습니다. - 선분을 순회하면서, 시작점이 현재 그룹의 끝점보다 크면 새로운 그룹이 시작되며 그룹 개수가 증가합니다. 그렇지 않다면 현재 그룹의 끝점을 업데이트합니다.
복잡도 분석
위 알고리즘의 시간 복잡도는 다음과 같습니다:
- 정렬 단계:
O(n log n) - 그룹 계산 단계:
O(n)
따라서 전체 시간 복잡도는 O(n log n)입니다.
결론
이번 문제를 통해 선분을 그룹으로 나누는 알고리즘을 구현해 보았습니다. 이 알고리즘은 선분들이 서로 겹치는 경우를 쉽게 처리할 수 있는 방법입니다. 코딩 테스트를 준비하면서 다양한 문제를 접하고, 문제 해결 방법을 고민하는 것이 실력을 쌓는 데 큰 도움이 됩니다. 앞으로 더 많은 알고리즘 문제에 도전하며 연습하시길 바랍니다!