문제를 나름대로 간소화하기 위해서 고민을 해 보았다.

이전에 두 수의 합이 최소가 되도록 하는 문제를 풀었던 기억을 기초로 하여

A,B,C,D의 배열에 수들이 들어가 있다면 A+B (Ai + Bj), C+D (Ci + Dj)으로 배열을 두개로 만들어,

A+B 배열과 C+D 배열의 인자들 중 합이 0이 되는 인자 i,j 쌍의 갯수를 구하는 문제로 생각하면 어떨까

시간이 12초인 만큼, 4000x4000 배열 두개를 활용하여 2x4000x4000만큼의 연산은 감당가능하기 떄문에 좋은 접근이라고 생각했다.

그 때와 일차적으로 다른 점은, 중복되는 수가 여러개가 있을 수 있다는 점이였는데,

삽입시에 자동으로 정렬이 되면서 중복된 키를 허용하는 multiset으로 컨테이너를 쓰기로 계획했다.

A+B, C+D 배열을 만드는 것은 너무 간단하고, 이제 이 정렬된 두 컨테이너에서 쌍을 찾는 알고리즘을 고민해보기로 했다.

A+B의 iterator을 aa, C+D의 iterator을 bb라 하면

1. *aa == *(aa+1)이거나, *bb == *(bb-1)이면 aa+1 혹은 bb-1 후 다시 비교를 시작한다

이런 식으로 시도해봤으나, 중복 경우 로직이 좀 쓸대없이 복잡하기도 하고,

set의 경우에는 iterator을 쓰더라도 불편하게 접근되는 감이 있어서 map을 쓰기로 했다

데이터가 큰 만큼 hash화 된 index로 속도가 빠르게 접근 가능한 map이 좋을거라고 생각했는데, 공간 초과가 발생했다.

unordered_map을 사용해도 마찬가지였고, (공간면에서는 차이가 크게 없겠지만 시간초과도 발생했었기에)

기존에 사용하지 않았던 std::unique를 통한 중복 아이템 제거 후 해당 index에 몇개의 중복되는 아이템이 있는지 count 벡터를 별도로 구성하여 구현하였다

void erase_unique(vector<int>& vec) {
	auto it = std::unique(vec.begin(), vec.end());
	vec.erase(it, vec.end());
}

void count_item(const vector<int>& arr, vector<int>& countarr) {
	int idx = 0, cnt = 0, val = 0;

	auto iter = arr.cbegin(); 

	val = *iter;
	cnt = 1;

	iter ++;

	for (;iter != arr.cend();iter++) {
		if (val != *iter) {
			countarr[idx++] = cnt;
			val = *iter;
			cnt = 1;
		} else
			cnt += 1;
	}
	countarr[idx] = cnt;
}

~ 첫 번째, 두 번째 아이템의 합을 AA 배열에 저장, BB도 마찬가지로 저장 ~

sort(AA.begin(), AA.end());
sort(BB.begin(), BB.end());

AAcount.resize(AA.size());
BBcount.resize(BB.size());

count_item(AA, AAcount);
count_item(BB, BBcount);

erase_unique(AA);
erase_unique(BB);

~ 로직 ~

구현의 편의성을 위해 문제를 조금 더 다르게 해석해 보았다.

Ai+Bj = 0  -> -Ai = Bj 이기 떄문에,

A,B,C,D의 배열에 수들이 들어가 있다면 -(A+B) -(Ai + Bj), C+D (Ci + Dj)으로 배열을 두개로 만들어,

A+B 배열과 C+D 배열의 인자들 중 값이 같은 인자 i,j 쌍의 갯수를 구하는 문제로 생각하면 어떨까

라고 생각하면 문제가 좀더 간편해지고, 두 비교하는 루틴도 아주 간단해지는 효과가 발생했다.

AA 배열의 index를 쓰면 iterator 대신 변수 하나씩만 써도 되겠지만, 기존 코드에 간단히 변형을 하여 구현을 했다.

unsigned long long cnt = 0;
for (auto aa = AA.begin(), bb = BB.begin(), aacnt = AAcount.begin(), bbcnt = BBcount.begin();;) {
	if ((*aa) == (*bb)) {
		cnt += (unsigned long long)(*aacnt) * (*bbcnt);
	}
	if (aa + 1 != AA.end() && bb + 1 != BB.end()) {
		if(*(aa+1) > *(bb+1)) {
			bb++;
			bbcnt++;
		}
		else {
			aa++;
			aacnt++;
		}
	} else if(aa + 1 != AA.end()) {
		aa++;
		aacnt++;
	}
	else if(bb + 1 != BB.end()) {
		bb++;
		bbcnt++;
	}
	else
		break;
}

좀더 개선할 여지가 있을수도 있겠지만, 골드2 문제에 이미 심력을 많이 쏟았기에, 여기서 만족하기로 했다.

제출을 최소화 하는게 옳은 방향성이라고 생각해서 제출을 spamming하지 않으려고 하는 편이지만, 이번에는 그 원칙을 지키지 못했다.

쉬운 문제라고 생각했으나, 생각보다는 편리한 컨테이너들에 대해 공간복잡도에 대해 많이 생각해볼 계기가 되는 문제였다. 공간복잡도와 시간복잡도면에서 문제가 발생하다보니, 내가 선택한 알고리즘 방식에 대해 맞나 싶은 의문도 많이 들었고, 사실 문제 자체는 워낙 쉬운 문제다 보니 여기서 끝났지만, 알고리즘 자체의 난이도와 공간복잡도도 따지는 문제가 주어진다면 난이도가 곱절로 어려워질 것이라고 느꼈다. 

5번동안 상하좌우로 슬라이딩하는 작업을 했을 떄의 결과 값중 최댓값을 구하는 문제이다.

다른 골드1에 비하면 너무 쉬운 문제라 생각하는데 많은 시간이 필요하지 않았다.

대신 '슬라이딩'하는 과정에서, 필요한 만큼의 탐색만 하는 방법을 고민했다.

말 그대로 슬라이딩으로 구현하는 것이 아니라, 행이나 열을 탐색을 할 때,

 이전 값을 저장 해 주는 변수를 사용해서 같은 값이 들어오면 합쳐서 새로운 위치에 *2를 해서 넣어주고,

 아니면 변수 값을 해당 위치에 넣고 변수에 현재 값을 넣어주는 식으로 구현하여

탐색이 다 끝난 시점에서 마지막 삽입 위치부터 끝까지는 0을 넣어주는 방식으로 구현했다.

vector<vector<int>> move_down(vector<vector<int>> arr) {
	for (int i = 0; i < arr.size(); i++) {
		int new_pos = arr[i].size() - 1, prev = -1;
		for (int j = arr[i].size() - 1; j >= 0; j--) {
			if (arr[j][i] == 0) continue;
			if (prev == -1)
				prev = arr[j][i];
			else if (prev == arr[j][i]) {
				arr[new_pos--][i] = prev * 2;
				prev = -1;
			}
			else {
				arr[new_pos--][i]= prev;
				prev = arr[j][i];
			}
		}
		if (prev != -1)
			arr[new_pos--][i] = prev;
		for (int j = new_pos; j >= 0; j--)
			arr[j][i] = 0;
	}

	return arr;
}

5번의 슬라이딩 방향을 탐색하는 건 정말 단순한 DFS로 구현했다.

int dfs(int cur, vector<vector<int>> arr) {
	int max = 0;
	if (cur == max_try) {
		return get_max(arr);
	}
	vector<int> dfs_result;
	dfs_result.push_back(dfs(cur+1, move_left(arr)));
	dfs_result.push_back(dfs(cur+1, move_right(arr)));
	dfs_result.push_back(dfs(cur+1, move_up(arr)));
	dfs_result.push_back(dfs(cur+1, move_down(arr)));

	for(auto &item : dfs_result)
		if(max < item)
			max = item;

	return max;
}

아쉬운 점은 두가지 있다.

1. move 해주는 코드를 하나로 통일하고 싶음

아예 같은 역할을 하는 코드들인데, 행인지 열인지, 오름차순인지 내림차순인지로 인해 함수를 4개로 나눴다.

처리를 하기 전에 컨테이너에 담고, 그 컨테이너를 넘겨주는 식으로 구현하면 핵심 부분은 하나로 통일 할 수 있을텐데

컨테이너을 거쳐서 처리하면 추가적인 부하가 생기기 떄문에 생각으로만 남겨두었다.

공간복잡도와 시간복잡도를 희생하지 않을 좋은 방법이 있다면 그것으로 대체하고 싶을 정도로 코드가 지저분하다.

2. 공간복잡도를 더 고려할 방법은 없을까

일반적으로 재귀호출을 처리할 떄, 값들을 reference로 넘겨주는 편인데, 단순 변수가 아닌 2차원 배열을 계속 복사하여 전달해주는 것이 공간복잡도면에서 굉장한 비효율이라고 생각했다.

내가 다른 DFS 문제에서 구현할 때는 재귀 밖으로 나왔을 떄 아래에서 다시 원래 상태로 복원해 주곤 했는데, 결국 그렇게 하면 시간복잡도와 공간복잡도 간의 tradeoff가 되어 먼저 제출을 하고 공간복잡도를 초과하면 해당 방식을 시도해볼까 했는데, 그대로 통과하여 수정하지 않았다.