라인 스위핑

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 사용한 알고리즘 : 풀이1_ 라인 스위핑, 풀이2_투 포인터 ※풀이 전략 2가지 전략으로 풀이를 해보았다. 풀이1. (라인 스위핑) 1. 입력받은 각각의 수를 튜플 형식으로 리스트에 추가한다. 만약 음수면 (abs(수), -1)로, 양수면 (수, 1) 형식으로 리스트에 추가한다. (abs는 절댓값 의미) 2. 리스트에 저장된 튜플들을 튜플의 첫 번째 원소로 ..

https://www.acmicpc.net/problem/19598 19598번: 최소 회의실 개수 서준이는 아빠로부터 N개의 회의를 모두 진행할 수 있는 최소 회의실 개수를 구하라는 미션을 받았다. 각 회의는 시작 시간과 끝나는 시간이 주어지고 한 회의실에서 동시에 두 개 이상의 회의 www.acmicpc.net 풀이 사용한 알고리즘 : 라인 스위핑 풀이전략 1. 시작점과 끝점에 대한 튜플 배열을 별개로 생성한다. 시작점의 튜플은 (시작점 위치, 1) 끝점의 튜플은 (끝점 위치, -1)로 만든다. 위 문제에서 주어진 예제 입력 1번을 예로들면 아래와 같다. 시작점 배열 = [ [0,1], [15,1], [5,1] ] 끝점 배열 = [ [40,-1], [30,-1], [10,-1] ] 2. 시작점 배열과..

https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net 풀이 사용한 알고리즘 : 라인 스위핑 ※ 풀이 전략 1. 입력 받은 선들을 시작점 기준으로 오름차순 정렬한다. 2. 맨 처음 입력한 선분의 시작점을 start, 끝점을 end로 둔다. 3. 다음 선의 시작점이 end보다 작으면 end는 해당 선의 끝점으로, 다음 선의 시작점이 end보다 크면 start는 해당 선의 시작점, end는 해당 선의 끝점으로 변경한다. 4..