스위핑1 [백준] 2170번 - 선 긋기 [Java] https://www.acmicpc.net/problem/2170 1. 아이디어 그리디 알고리즘과 스위핑 알고리즘으로 해결할 수 있었다.2. 문제풀이 일반적인 그리디 알고리즘이랑 스위핑 두 가지 방식으로 접근했다.그리디 알고리즘은 선의 x 좌표를 기준으로 오름차순 정렬한 우선순위 큐(items)와 y 좌표를 기준으로 내림차순 정렬한 우선순위 큐(pq) 두 개를 사용했다. items에서 원소(item)를 하나씩 꺼내서 pq의 원소(cur)와 비교하며 item과 cur이 겹치는 부분이 있으면 두 선을 합친 선을 pq에 다시 삽입하고 겹치는 부분이 없으면 각각 삽입하는 방식으로 구현했다. 이후 pq의 모든 선을 꺼내서 길이를 합하면 된다.스위핑은 x 좌표를 기준으로 오름차순, x 좌표가 같으면 y 좌표를 기.. 2025. 3. 7. 이전 1 다음
