[Python][백준] 2170. 선 긋기/ 정렬,스위핑 (G5)

🔗링크 :  

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

---

🗒️파이썬 코드 풀이

N = int(input())
lst = []

for _ in range(N):
    a,b = map(int,input().split())
    lst.append([a,b])

lst.sort()
merged = []

# 초기값 설정
start, end = lst[0][0],lst[0][1]

for i in range(1,N):
    a,b = lst[i][0],lst[i][1]
    if a <= end :
        end = max(end,b)
    else: 
        merged.append([start,end])
        start, end = a, b

merged.append([start,end])



print(sum([merged[i][1]-merged[i][0] for i in range(len(merged))]))

 

 

1.두 점의 위치를 lst에 전부 넣어주고 sort로 정렬 해준다.

• 여기에서 sort를 사용해도 된다. ( 정렬 시간 복잡도는 N*LogN | 10^6 * Log10^6 = 약 10^7)

2. 초기값을 정렬된 lst의 첫번째 원소를 기준으로 한다.

 

3. 이후 1부터 N 까지 반복문을 돌리면서 스위핑을 진행해준다. 

• 비교 할 두 점을 a,b 로 설정
• a가 start와 end 사이에 있는 경우 
  • 이 경우는 end를 max로 갱신해준다.
• a가 start와 end 밖에 있는 경우
  • 이 경우는 기존의 start와 end를 merged 리스트에 삽입
  • 이후 새로운 start와 end 설정 

4. 완료를 하면 아직 merged 리스트에 삽입되지 않은 마지막 start와 end를 append 한다. 

 

---

📌 문제 코멘트 

 

• 이 문제는 정렬 알고리즘을 쓰지 못했다.
  
  • 쓰지 못한 이유로는 직접 시간 복잡도를 계산하지 않고, '대충 안될것 같아' 라는 생각 때문이였다. 
  • 결국에는 더 어렵게 접근했고, 풀제 풀이도 실패했다.
  • 좀 애매한 것은 꼭 시간 복잡도를 계산해보자.
• 정렬 알고리즘을 한 후에, start와 end를 계속 갱신하는 부분도 헷갈렸다.
  • 이 부분을 스위핑이라 하는데, 잘 기억해두자.
  • 또한 새로운 merged 리스트를 두어 append 하는 방식도 기억하자.
• 이 문제 풀이에서 가장 중요한 부분은 새로운 start와 end로 merged 리스트를 채우는 것

---

📚문제

매우 큰 도화지에 자를 대고 선을 그으려고 한다. 선을 그을 때에는 자의 한 점에서 다른 한 점까지 긋게 된다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없다고 하자.

이와 같은 식으로 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하시오. 선이 여러 번 그려진 곳은 한 번씩만 계산한다.

입력

첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다.

출력

첫째 줄에 그은 선의 총 길이를 출력한다.

예제 입력 1 복사

4
1 3
2 5
3 5
6 7

예제 출력 1 복사

5