[알고리즘/그리디] 2170번 : 선 긋기 - python

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

2170번: 선 긋기

 

---

• 문제
• 소요시간: 47분 10초

---

• 설계하기(접근방법) 

1. 입력받기

배열을 입력받는다

 

2. 구현하기

먼저 1차원 배열을 left를 기준으로 정렬한다

 

그 후 케이스를 나누어서 더해나가야 한다

 

이전 left, right

현재 n_left, n_right

 

케이스 1)

1 4

2 5 인 경우

 

이전의 for문에서 4 -1만큼 cnt에 더해주고

이전 right인 4를 넘겨준다

 

현재의 n_left가 이전의 right보다 작으니

현재 n_right에서 이전의 right를 빼준 값을 nt에 대한다

 

케이스 2)

1 4

2 3 인 경우

 

n_right가 right보다 작으니 pass한다

 

케이스 3)

1 4

5 6

 

n_left가 right보다 크니 현재 6 -5 만큼 더해준다

 

이 케이스 후 공통적으로

지금까지의 right 값중 max값을 right로 갱신해야 한다

 

1 4

2 3 일때 만약 다음이

3 4 인 경우 4-3 을 더해주면 안되기에

지금까지의 최대값을 빼주어야 한다

4 - 4 = 0

 

3. 출력하기

더해나간 길이를 출력한다

 

---

• 코드(출력)

import sys 
input = sys.stdin.readline

n = int(input())

length = []

for i in range(n):
    x, y = map(int, input().split())
    length.append([x,y])

length.sort(key = lambda x: (x[0], x[1]))
left, right = length[0][0], length[0][1]
cnt = right - left

for i in range(1, len(length)):
	# 현재 항목
    n_left, n_right = length[i][0], length[i][1]
    if n_left >= right:
        cnt += (n_right - n_left)
    elif n_left < n_right :
        if n_right <= right:
            pass
        else: 
            cnt += (n_right - right)
    # 다음 변수 선언
    if right >= n_right:
        pass
    else:
        right = n_right
        
    
print(cnt)

---

• 얻어갈 부분

1. n 이 100만개일 때도 sort()가 가능하다. 안되는 줄 알고 고민했었는데, 앞으로는 주의하자