[C++] 백준(BOJ) - 2170 : 선 긋기

25 Mar 2024 in Develop on C++, Algorithm Last modified at: 2024-05-20

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 2170 : 선 긋기(링크)

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

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

입력

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

출력

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

알고리즘

1. 정렬
2. 라인스위핑

풀이

• Counting Array
  • 20억 공간복잡도상 문제 풀이 힘듦
• 라인스위핑하며 총 길이를 더하기
  • 시작 지점 기준 정렬
• 라인스위핑하며 개수 카운팅 (곂치지 않는 지점 찾기)
  • 끝 지점 기준 정렬

코드

// BOJ-2170 : 선 긋기
#include <bits/stdc++.h>
using namespace std;

int n, s, e, res;
vector<pair<int, int>> v;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> s >> e;
		v.push_back({ s, e });
	}
	sort(v.begin(), v.end());

	s = v[0].first;
	e = v[0].second;
	res = e - s;

	for (int i = 1; i < n; i++)
	{
		if (e > v[i].second) continue;
		else
		{
			if (v[i].first < e) {
				res += v[i].second - e;
				e = v[i].second;
			}
			else
			{
				res += v[i].second - v[i].first;
				s = v[i].first;
				e = v[i].second;
			}
		}
	}

	cout << res << '\n';

	return 0;
}

평가

• 카운팅 배열을 통한 접근
  • 시간복잡도, 공간복잡도 고려했을 때, 벗어난다면 다른 방법 고려
• 라인스위핑
  • 단순히 개수 증가만 하는 경우 end 지점 기준 정렬 후 그리디 방법으로 푸리
  • 현재 지점과 다음 지점 상황에 맞게 분기를 잘 나누어서 로직 만들기