[코드트리 챌린지] 3주차 - +1-1 Technique / 가장 많이 겹치는 구간

https://www.codetree.ai/landing/level-test/6289/result/4?&utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

문제 분석

문제는 여러 개의 구간이 주어졌을 때, 가장 많이 겹치는 부분에서 몇 개의 구간이 겹치는지를 찾는 것입니다. 간단한 예를 들면, 구간 [2, 16]과 [4, 6]은 4에서 6까지 겹칩니다. 이러한 방식으로 모든 구간들이 얼마나 겹치는지를 파악하고 가장 많이 겹치는 부분을 찾아야 합니다.

풀이 방법

1. 각 구간의 시작점과 끝점을 점으로 생각합니다.
2. 구간이 시작할 때마다 겹치는 구간의 수를 증가시키고 (1을 더하고), 구간이 끝날 때마다 감소시킵니다 (-1을 뺍니다).
3. 이렇게 생성된 점들의 리스트를 정렬하여, 작은 점부터 큰 점 순서로 순회합니다.
4. 정렬된 점들을 순회하면서 겹치는 구간의 수를 계산합니다.
5. 가장 큰 겹치는 구간의 수를 출력합니다.

n = int(input())
lines = [tuple(map(int, input().split())) for _ in range(n)]

# 각 구간의 시작과 끝점을 나타내는 리스트를 생성합니다.
points = []
for start, end in lines:
    points.append((start, 1))    # 시작점 (겹치는 구간 수 증가)
    points.append((end, -1))     # 끝점 (겹치는 구간 수 감소)

# 점들을 정렬하여 순서대로 점검할 수 있게 합니다.
points.sort()

cnt = 0       # 현재 겹치는 구간의 수
max_cnt = 0   # 최대로 겹친 구간의 수

# 정렬된 점들을 순회하며 겹치는 구간의 수를 계산합니다.
for point, value in points:
    cnt += value
    max_cnt = max(cnt, max_cnt)

print(max_cnt)

코드 설명

1. 먼저, 입력 받은 구간들을 기반으로 각 구간의 시작점과 끝점을 나타내는 points 리스트를 생성합니다.
2. 시작점은 겹치는 구간의 수를 증가시키기 위해 1의 값을 가지고, 끝점은 겹치는 구간의 수를 감소시키기 위해 -1의 값을 가집니다.
3. 점들을 순서대로 점검하기 위해 points 리스트를 정렬합니다.
4. 정렬된 점들을 순회하며, 현재 겹치는 구간의 수(cnt)와 최대로 겹친 구간의 수(max_cnt)를 계산합니다.
5. 결과적으로, max_cnt에 가장 많이 겹치는 구간의 수가 저장됩니다.

해당 방법을 통해 간단하게 가장 많이 겹치는 구간의 수를 구할 수 있습니다.

지난주보다 소폭 상승하였다. 이번주에는 공부를 많이 못한 만큼 발전이 적은 것 같다. 더 열심히 공부해야겠다.