[코드트리 챌린지] 다섯번째 학습진단

오늘은 학습진단에서 +1 -1 Technique 문제를 만났다.

여러 길이의 선분이 주어졌을 때, 겹치는 선분들의 점수의 합이 k 점을 넘는 구간의 총 길이를 구하는 문제였다.

이전에 이번 문제와 유사한 겹치는 선분의 개수를 구하는 문제를 접했을 때

priority queue를 활용했던 것을 기억해서 heapq를 사용하여 접근했다.

하지만 k 점을 넘는 구간의 총 길이를 어떻게 구해야 하는지 고민하다가 결국 시간 초과로 틀렸다.

 

덕분에 코드트리에서 "진단에서 부족했던 유형"으로 +1 -1 Technique 개념을 소개한 내용을 보았는데,

겹치는 선분의 개수 문제에 대한 새롭고 심플한 풀이 방법을 만날 수 있어서 굉장히 흥미로웠다.

상황에 맞게 +1 과 -1을 활용하여 문제를 해결하는 방법으로

구간의 시작점에서는 +1, 구간의 끝점에서는 -1 을 함으로써 겹치는 구간의 개수를 파악할 수 있다.

 

추가로 k 점을 넘는 구간의 총 길이는 시작점에는 x를 더하고 끝점에서는 x를 빼면서

총점을 k와 비교하며 길이를 구할 수 있을 것 같다.

다음에는 이 방법을 사용해 문제를 풀어볼 것이다.

 

유사 문제 풀이

코드 트리 문제

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

백준 문제

https://www.acmicpc.net/problem/1689

 

문제

n 개의 구간이 주어졌을 때 최대 몇 개의 구간이 겹치는지 구하는 문제이다.

코드

백준 문제에서는 pypy로 제출해야 시간 초과가 안 난다.

 

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

points = []
for x1, x2 in segments:
    points.append((x1, +1)) # 시작점
    points.append((x2, -1)) # 끝점

# 정렬을 진행합니다.
points.sort()

# 가장 겹치는 선분이 많을 때의 선분 개수 저장할 변수
ans = 0
# 각 위치에 적혀있는 숫자들의 합을 구해줍니다.
sum_val = 0
for x, v in points:
    # 적혀있는 가중치를 전부 더해줍니다.
    sum_val += v
    
    # ans 업데이트
    ans = max(ans,sum_val)

print(ans)

 

 

 

---

#코드트리 #코딩테스트 #코딩테스트실력진단