[PS]#Gridland Metro

 

---

 

https://www.hackerrank.com/challenges/gridland-metro/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign

Gridland Metro | HackerRank

 

#define PII pair<int, int>
#define LL long long

long long gridlandMetro(int n, int m, int k, vector<vector<int>> track)
{
	LL N = n, M = m;
	LL total = N * M;

	vector<int> idxies;
	map<LL, vector<PII>> mmm;

	for (int i = 0; i < k; ++i)
	{
		LL idx = track[i][0], r1 = track[i][1], r2 = track[i][2];

		if(mmm.find(idx) == mmm.end()) idxies.push_back(idx);
		mmm[idx].push_back({ r1, r2 });
	}

	for (LL i = 0; i < idxies.size(); ++i)
	{
		LL idx = idxies[i];
		sort(mmm[idx].begin(), mmm[idx].end());

		LL f = 0, s = LLONG_MAX, bfF = 0, bfS = LLONG_MAX;
		for (int o = 0; o < mmm[idx].size(); ++o)
		{
			f = mmm[idx][o].first, s = mmm[idx][o].second;

			if (bfS < f)
			{
				total -= bfS - bfF + 1;
				bfF = f, bfS = s;
				continue;
			}
			f = (bfF == 0) ? bfF = f : bfF = min(bfF, f);
			s = (bfS == LLONG_MAX) ? bfS = s : bfS = max(bfS, s);

		}
		if (bfF != 0) total -= bfS - bfF + 1;
	}

	return total;
}

 

 

* 문제 풀이 과정

 

위 문제의 핵심은 "범위의 중복을 어떻게 처리할 것인가" 에 달려있다.

이전 값과 현재 값을 저장해가면서 이전 값의 마지막이 현재 값의 첫번째 값보다 작아질 때, 계산한다.

{ 1, 4 } -> { 2, 7 } => 통과.

{ 1, 4 } -> { 5 ,7 } => 계산.

 

어떤 반복적인 계산보다 주어진 데이터를 즉각 계산해서 시간을 줄이는 것이 관건이다.

 

또, track 을 행렬로 표현할 수 없다.

n,m 각각 10 의 9승 이기 때문에 메모리가 부족하다.

bool [100000001] 로 선언할 수 있지만 이런 방식의 접근은 혼란만 준다.

 

index 를 담을 수 있는 배열을 만들었고 index 에 해당하는 행을 바로 찾기 위해서 map 을 사용했다.

 

 

 

 

* 해결 과정 문제점

 

논리적 문제.

 

항상 조심해야하지만,

for 문 안에서 어떤 계산을 구현해야할 때 논리적 오류로 인해서 답이 다르게 나오는 경우가 많다.

너무 신경 쓸게 많고 정신 없기 때문이지만 단계별로 생각하는 습관을 길러야할 것이다.

또, 코드를 보면서 하나하나 논리적으로 틀린 부분을 찾아야만 한다.

그것 외엔 딱히 방법이 없어보인다.

 

이 문제에선 (조건식) ? : 에서 bfF, bfS 에 값을 다시 넣어주지 않았다..